Merge Overlapping Events in the Same Hall - Solution & Explanation

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.