LeetCode 2494 - Merge Overlapping Events in the Same Hall

Difficulty: 🔴 Hard
Topics: Database

Solution

Problem Understanding

The problem requires us to merge overlapping events in the same hall. Each row of the HallEvents table represents an event in a particular hall with a start_day and an end_day. Events are considered overlapping if they share at least one day in common. The goal is to return a table of merged events such that no two events in the same hall overlap.

The input is a relational table with potentially duplicate rows. The output is a table of merged events where overlaps within each hall are resolved. Key constraints include: events are hall-specific, duplicates may exist, and dates are inclusive. Edge cases include consecutive events (where the end day of one event is the start day of another) and events entirely contained within another event.

Understanding these constraints clarifies that we must handle each hall independently and consider inclusive overlaps.

Approaches

The brute-force approach would involve comparing every event in a hall to every other event in the same hall. If they overlap, we merge them into a new event and repeat until no overlaps remain. This works logically but is inefficient, with potentially O(n²) comparisons per hall, which is slow for large datasets.

The optimal approach relies on sorting events by start_day for each hall. Once sorted, we can iterate through events, merging consecutive events if they overlap. Sorting ensures we only need a single pass per hall, as any overlap must occur with the next event or a chain of subsequent events. This reduces complexity and simplifies the logic.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(n)	Compare every event with every other in the same hall, merge iteratively
Optimal	O(n log n)	O(n)	Sort events by start date per hall and merge in one pass

Algorithm Walkthrough

Group all events by hall_id to process each hall independently. This ensures that overlaps are only considered within the same hall.
For each hall, sort its events by start_day. Sorting allows us to guarantee that any overlap occurs with consecutive events, simplifying merging.
Initialize an empty list to hold merged events for the current hall.
Iterate through the sorted events. If the list of merged events is empty, add the first event. Otherwise, compare the start_day of the current event with the end_day of the last merged event.
If the current event overlaps or touches the last merged event (inclusive), update the end_day of the last merged event to be the maximum of the last merged end_day and the current end_day.
If there is no overlap, append the current event as a new merged event.
After processing all events in the hall, add the merged results to the final output list.
Repeat steps 2-7 for each hall and return the combined results.

Why it works: Sorting guarantees that overlapping events are consecutive. By always extending the end_day of the last merged event when overlap occurs, we ensure that all overlapping events are combined correctly. Non-overlapping events naturally start a new merged event, preserving correctness.

Python Solution

from typing import List
import collections

class Solution:
    def mergeEvents(self, hallEvents: List[List[str]]) -> List[List[str]]:
        # Group events by hall_id
        events_by_hall = collections.defaultdict(list)
        for hall_id, start_day, end_day in hallEvents:
            events_by_hall[hall_id].append([start_day, end_day])
        
        merged_result = []
        for hall_id, events in events_by_hall.items():
            # Sort events by start_day
            events.sort(key=lambda x: x[0])
            merged = []
            for start, end in events:
                if not merged or merged[-1][1] < start:
                    merged.append([start, end])
                else:
                    merged[-1][1] = max(merged[-1][1], end)
            for start, end in merged:
                merged_result.append([hall_id, start, end])
        
        return merged_result

Explanation: First, we group events by hall using a dictionary. Sorting ensures we only need one pass per hall to merge overlapping intervals. The merge logic updates the end_day of the last interval when an overlap occurs and appends a new interval if there is no overlap. Finally, we reconstruct the merged events with the corresponding hall_id.

Go Solution

package main

import (
    "sort"
)

type Event struct {
    hallID   int
    startDay string
    endDay   string
}

func mergeEvents(hallEvents [][]interface{}) [][]interface{} {
    eventsByHall := make(map[int][][2]string)
    
    for _, event := range hallEvents {
        hallID := event[0].(int)
        startDay := event[1].(string)
        endDay := event[2].(string)
        eventsByHall[hallID] = append(eventsByHall[hallID], [2]string{startDay, endDay})
    }
    
    result := [][]interface{}{}
    
    for hallID, events := range eventsByHall {
        sort.Slice(events, func(i, j int) bool {
            return events[i][0] < events[j][0]
        })
        
        merged := [][2]string{}
        for _, e := range events {
            if len(merged) == 0 || merged[len(merged)-1][1] < e[0] {
                merged = append(merged, e)
            } else {
                if e[1] > merged[len(merged)-1][1] {
                    merged[len(merged)-1][1] = e[1]
                }
            }
        }
        
        for _, m := range merged {
            result = append(result, []interface{}{hallID, m[0], m[1]})
        }
    }
    
    return result
}

Explanation: The Go version mirrors the Python approach. Events are grouped in a map and sorted by startDay. We merge overlaps by comparing the current event with the last in the merged slice. The use of slices and type assertion reflects Go's type system and differs slightly from Python's dynamic typing.

Worked Examples

Example 1:

Input Hall 1:

["2023-01-13", "2023-01-14"]
["2023-01-14", "2023-01-17"]
["2023-01-18", "2023-01-25"]

Sorting gives the same order. Merging:

First interval ["2023-01-13", "2023-01-14"] → added to merged
Second interval ["2023-01-14", "2023-01-17"] → overlaps, merged to ["2023-01-13", "2023-01-17"]
Third interval ["2023-01-18", "2023-01-25"] → no overlap, added as new

Result: ["2023-01-13", "2023-01-17"], ["2023-01-18", "2023-01-25"]

Hall 2:

["2022-12-09", "2022-12-23"]
["2022-12-13", "2022-12-17"]

Merged to ["2022-12-09", "2022-12-23"]

Hall 3: single interval remains unchanged.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Sorting events per hall dominates; n is the total number of events
Space	O(n)	For storing grouped events and merged results

Sorting is necessary to ensure linear merging. Grouping by hall ensures correctness and does not exceed O(n) extra space.

Test Cases

# Provided example
assert Solution().mergeEvents([
    [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"]
]) == [
    [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"]
]

# Edge cases
assert Solution().mergeEvents([]) == []  # empty input
assert Solution().mergeEvents([
    [1, "2023-01-01", "2023-01-01"]
]) == [[1, "2023-01-01", "2023-01-01"]]  # single day event
assert Solution().mergeEvents([
    [1, "2023-01-01", "2023-01-05"],
    [1, "2023-01-05", "2023-01-10"]
]) == [[1, "2023-01-01", "2023-01-10"]]  # consecutive events
assert Solution().mergeEvents([
    [1, "202