2494 — Merge Overlapping Events in the Same Hall [LeetCode]

Question: Write an SQL query 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. (For the full code, please visit my GitHub repository)

HallEvents:

Output:

Solution:

To effectively merge overlapping events within each hall, we need to start by identifying which events overlap. After that, the key is to group events that share common days by an indicator. This indicator can be determined by checking if the start_day of an event falls within the date range of the previous event in an ordered sequence.

Logically, an event overlaps with the previous one if its start_day is less than or equal to the previous event's end_day. To achieve this, we can use the LAG() window function.

This logic is demonstrated in the following SQL code:

SELECT 
    *, 
    LAG(end_day) OVER(PARTITION BY hall_id ORDER BY start_day, end_day) AS previous_end_day, 
    IIF(
        LAG(end_day) OVER(PARTITION BY hall_id ORDER BY start_day, end_day) >= start_day, 
        'Yes', 
        'No'
    ) AS overlap
FROM 
    HallEvents;

While Yes and No can indicate overlaps, they aren't suitable for grouping events effectively since they don't provide unique identifiers for each group. To create a more specific indicator, we can assign numeric values: 1 for No (no overlap) and 0 for Yes (overlap).

By using the SUM() window function to cumulatively add these values, we can achieve our goal. The 0 values won't change the cumulative sum, meaning that if an event overlaps with the previous one (i.e., Yes), it will inherit the same group indicator as the previous event. This continues until we encounter a non-overlapping event (No), where the indicator will increment, marking the start of a new group.

This approach allows us to generate unique group identifiers for each set of overlapping events, enabling effective grouping and merging in the subsequent steps.

WITH CTE AS 
(
    SELECT *, 
           IIF(LAG(end_day) OVER(PARTITION BY hall_id ORDER BY start_day, end_day) >= start_day, 0, 1) AS overlap
    FROM HallEvents
)

    SELECT *, 
           SUM(overlap) OVER(PARTITION BY hall_id ORDER BY start_day, end_day) AS indicator
    FROM CTE; 

Result:

With our group indicators in place, the final step is to group the events within each hall based on these indicators. Then, we’ll calculate the earliest start_day and the latest end_day for each group, effectively merging the overlapping events.

-- Use Common Table Expressions (CTE) to identify and merge overlapping events within the same hall

WITH CTE AS 
(
    -- Compare to find the overlap based on the previous event's end_day
    SELECT *, 
           IIF(LAG(end_day) OVER(PARTITION BY hall_id ORDER BY start_day, end_day) >= start_day, 0, 1) AS overlap
    FROM HallEvents
), 

T AS 
(
    -- Calculate the indicator to prepare for merging
    SELECT *, 
           SUM(overlap) OVER(PARTITION BY hall_id ORDER BY start_day, end_day) AS indicator
    FROM CTE
)

-- Final query to merge overlapping events by grouping them and selecting the minimum start_day and maximum end_day for each group
SELECT hall_id, 
       MIN(start_day) AS start_day, 
       MAX(end_day) AS end_day 
FROM T
GROUP BY hall_id, indicator
ORDER BY hall_id, start_day, end_day;

In this article, we’ve walked through the process of merging overlapping events within the same hall using SQL. By first identifying overlaps, then creating unique group indicators, and finally merging the events based on these groups, we’ve seen how powerful SQL can be in handling complex data scenarios.

I hope this guide has provided you with a clear and practical way to handle overlapping events in SQL. Feel free to experiment with the concepts and adapt them to your specific needs. Happy querying!