Leetcode 56. Merge Intervals

Problem

You are building a meeting room scheduling system. Given a collection of time intervals where each interval is represented as [start, end], consolidate all overlapping or adjacent intervals into the minimum number of non-overlapping intervals.

Two intervals overlap if one starts before or exactly when the other ends. For example, [1,3] and [2,6] overlap, and [1,4] and [4,5] are adjacent (touching at point 4) and should be merged.

Return the consolidated list of intervals.

Requirements

1. Merge all overlapping intervals into single intervals
2. Merge adjacent intervals that touch at their endpoints
3. Return the minimum number of intervals needed to cover all the original intervals
4. The output intervals should be sorted by their start times
5. Each interval is guaranteed to have start <= end

Constraints

• 1 ≤= intervals.length ≤= 10,000
• intervals[i].length == 2
• 0 ≤= start ≤= end ≤= 10,000
• The input may be unsorted

Examples

Example 1:

Input: intervals = [[1,3],[2,6],[8,10],[15,18]] Output: [[1,6],[8,10],[15,18]] Explanation: Since intervals [1,3] and [2,6] overlap, merge them into [1,6].

Example 2:

Input: intervals = [[1,4],[4,5]] Output: [[1,5]] Explanation: Intervals [1,4] and [4,5] are considered overlapping (they touch at 4).

Example 3:

Input: intervals = [[1,10],[2,3],[4,5],[6,7],[8,9]] Output: [[1,10]] Explanation: All smaller intervals are contained within [1,10], so they all merge.

Hint 1: Sorting Start by sorting the intervals. What property should you sort by? Consider how this makes it easier to detect overlaps.

Hint 2: Greedy Approach Once sorted, you can iterate through the intervals once. Keep track of the "current" interval you're building. When should you extend it versus starting a new one?

Hint 3: Overlap Condition Two intervals [a, b] and [c, d] overlap if c <= b (assuming they're sorted so a <= c). If they overlap, the merged interval is [a, max(b, d)].

Full Solution ` def consolidateIntervals(intervals): # Edge case: empty or single interval if not intervals or len(intervals) <= 1: return intervals

# Sort intervals by start time
intervals.sort(key=lambda x: x[0])

# Initialize result with the first interval
merged = [intervals[0]]

# Iterate through remaining intervals
for i in range(1, len(intervals)):
    current = intervals[i]
    last_merged = merged[-1]
    
    # Check if current interval overlaps or touches the last merged interval
    if current[0] <= last_merged[1]:
        # Merge by extending the end time to the maximum
        last_merged[1] = max(last_merged[1], current[1])
    else:
        # No overlap, add current interval as a new separate interval
        merged.append(current)

return merged

`

Approach:

1. Sort the intervals by their start times. This ensures we process intervals in chronological order, making it easy to detect overlaps.

2. Initialize a result list with the first interval as our starting point.

3. Iterate through remaining intervals:

   • Compare each interval with the last interval in our merged result
   • If the current interval's start is less than or equal to the last merged interval's end, they overlap or touch
   • When overlapping, extend the end time to be the maximum of both intervals' end times
   • If not overlapping, add the current interval as a new separate interval

4. Return the merged intervals which now represent the minimum set of non-overlapping intervals.

Time Complexity: O(n log n) where n is the number of intervals. The sorting step dominates the runtime.

Space Complexity: O(n) for the output array. If we exclude the output space and consider only auxiliary space, it's O(1) since we modify in-place or use constant extra space (depends on the sorting algorithm used).