Skip to main content
Talentd

Merge Overlapping Events in the Same Hall - Solution & Explanation

HardPremiumFree on FleetCodeDatabase4 min read
Practice this problem

Problem Statement

Table: HallEvents

+-------------+------+
| Column Name | Type |
+-------------+------+
| hall_id     | int  |
| start_day   | date |
| end_day     | date |
+-------------+------+
This table may contain duplicates rows.
Each row of this table indicates the start day and end day of an event and the hall in which the event is held.

 

Write a solution to merge all the overlapping events that are held in the same hall. Two events overlap if they have at least one day in common.

Return the result table in any order.

The result format is in the following example.

 

Example 1:

Input: 
HallEvents table:
+---------+------------+------------+
| hall_id | start_day  | end_day    |
+---------+------------+------------+
| 1       | 2023-01-13 | 2023-01-14 |
| 1       | 2023-01-14 | 2023-01-17 |
| 1       | 2023-01-18 | 2023-01-25 |
| 2       | 2022-12-09 | 2022-12-23 |
| 2       | 2022-12-13 | 2022-12-17 |
| 3       | 2022-12-01 | 2023-01-30 |
+---------+------------+------------+
Output: 
+---------+------------+------------+
| hall_id | start_day  | end_day    |
+---------+------------+------------+
| 1       | 2023-01-13 | 2023-01-17 |
| 1       | 2023-01-18 | 2023-01-25 |
| 2       | 2022-12-09 | 2022-12-23 |
| 3       | 2022-12-01 | 2023-01-30 |
+---------+------------+------------+
Explanation: There are three halls.
Hall 1:
- The two events ["2023-01-13", "2023-01-14"] and ["2023-01-14", "2023-01-17"] overlap. We merge them in one event ["2023-01-13", "2023-01-17"].
- The event ["2023-01-18", "2023-01-25"] does not overlap with any other event, so we leave it as it is.
Hall 2:
- The two events ["2022-12-09", "2022-12-23"] and ["2022-12-13", "2022-12-17"] overlap. We merge them in one event ["2022-12-09", "2022-12-23"].
Hall 3:
- The hall has only one event, so we return it. Note that we only consider the events of each hall separately.

Approach Overview

Problem Overview: You are given event records for halls where each event has a start and end day. Some events in the same hall overlap or touch each other. The goal is to merge those overlapping intervals and return the consolidated date ranges per hall.

Approach 1: Self-Join Interval Expansion (O(n²) time, O(n) space)

The most direct SQL approach compares every interval with other intervals in the same hall using a self join. Two events overlap when start_day <= other_end_day and end_day >= other_start_day. By repeatedly merging these ranges with MIN(start_day) and MAX(end_day), you can collapse overlapping intervals into larger blocks. This works but becomes expensive because every row potentially compares with many others. With large event tables the quadratic comparisons make it impractical.

Approach 2: Gaps and Islands with Window Functions (O(n log n) time, O(n) space)

The efficient solution treats overlapping intervals as an island detection problem. First sort events by hall_id and start_day. Then use a window function like LAG() or a running MAX(end_day) to detect when a new interval no longer overlaps the previous merged range. Whenever start_day is greater than the running maximum end, a new group begins. Assign a group id using cumulative sums, then aggregate each group with MIN(start_day) and MAX(end_day). This is the classic SQL gaps-and-islands technique and scales well since the database only performs sorting and linear window scans.

Window functions make the logic concise and performant. MySQL computes the running comparisons in a single pass after sorting, avoiding expensive cross joins. If you frequently solve interval merging problems in SQL, mastering this pattern is essential.

Conceptually this is similar to interval merging problems in algorithm interviews, but implemented using SQL analytics instead of arrays. The same pattern appears in scheduling systems, calendar consolidation, and booking platforms.

Recommended for interviews: The window-function gaps-and-islands approach is what interviewers expect. Mentioning the naive self-join shows you understand interval overlap detection, but using analytic functions demonstrates strong SQL skills and scales to large datasets. Related patterns appear frequently in database, SQL, and window function problems.

Solution

Code

MySQL

MySQL

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Self-Join Interval MergeO(n²)O(n)Small datasets or when window functions are unavailable
Window Function Gaps and IslandsO(n log n)O(n)General case in modern SQL engines like MySQL 8+, PostgreSQL, SQL Server
Recursive CTE Interval MergeO(n log n)O(n)Useful when building intervals step‑by‑step or when window functions are limited

Video Solution

Amazon Data Engineer SQL Interview Problem | Leetcode Hard SQL 2494 | Recursive CTE • Ankit Bansal • 23,805 views views

Watch 1 more video solutions →

Frequently Asked Questions

Is Merge Overlapping Events in the Same Hall easy or hard?
The problem is classified as Hard because it requires translating the interval merging concept into SQL using window functions or gaps-and-islands logic. Developers comfortable with analytic SQL functions usually find the pattern manageable once they recognize the grouping technique.
Merge Overlapping Events in the Same Hall Python/Java solution
In Python or Java, the typical approach sorts intervals by start time and iterates once while maintaining the current merged interval. If the next interval overlaps, extend the end boundary; otherwise store the current interval and start a new one. This algorithm runs in O(n log n) time with O(n) space for the merged output.
How to solve Merge Overlapping Events in the Same Hall in O(n)?
Pure O(n) is difficult in SQL because interval merging requires ordering by start time. The practical approach is O(n log n) using sorting plus window functions. After ordering the rows, compute a running maximum end_day and group intervals whenever the next start_day exceeds that maximum.
What is the best approach for Merge Overlapping Events in the Same Hall?
The best approach uses the SQL gaps-and-islands technique with window functions. Sort events by hall and start_day, compute a running maximum end_day, and start a new group when the next start_day exceeds that value. Then aggregate each group using MIN(start_day) and MAX(end_day). This runs in O(n log n) time due to sorting and scales well for large tables.
Is Merge Overlapping Events in the Same Hall asked at Google/Amazon/Meta?
Interval merging and gaps-and-islands problems appear frequently in data engineering and SQL interviews at companies like Google, Amazon, and Meta. Variants include merging meeting intervals, consolidating booking ranges, or detecting continuous activity periods.
What data structure is used in Merge Overlapping Events in the Same Hall?
In SQL solutions the main tools are window functions and ordered result sets rather than traditional data structures. Conceptually the algorithm relies on interval merging and running maximum tracking, which is similar to array interval merging used in algorithm problems.
What is the time complexity of Merge Overlapping Events in the Same Hall?
The optimal SQL solution runs in O(n log n) time because the database must sort events by hall_id and start_day before applying window functions. After sorting, the window scan and grouping operate in linear time. Space complexity is O(n) for intermediate result sets during grouping.

Ready to solve this problem?

Practice Merge Overlapping Events in the Same Hall with our built-in code editor and test cases.

Practice on FleetCode
Previous

Combine Two Tables

Next

Second Highest Salary