Problem Description

You are given an array of intervals where each interval is represented as [start_i, end_i]. Your task is to merge all overlapping intervals and return an array containing only non-overlapping intervals that cover all the original intervals.

Two intervals overlap if one starts before or when the other ends. For example:

• [1, 3] and [2, 6] overlap and should be merged into [1, 6]
• [1, 4] and [4, 5] overlap (they share the endpoint 4) and should be merged into [1, 5]
• [1, 2] and [3, 4] do not overlap and remain separate

The solution works by first sorting all intervals by their start points. Then it traverses through the sorted intervals, maintaining a current interval [st, ed]. For each new interval [s, e]:

• If the current interval's end ed is less than the new interval's start s, they don't overlap, so the current interval is added to the result and a new current interval begins
• Otherwise, they overlap, so the current interval is extended by updating ed to be the maximum of ed and e

After processing all intervals, the final current interval is added to the result. This ensures all overlapping intervals are merged into single continuous ranges.

Intuition

The key insight is that if we arrange intervals in a sorted order, overlapping intervals will naturally be positioned next to each other. Think about it visually on a number line - if intervals overlap, they must be adjacent or close to each other when sorted by their starting points.

Once sorted, we can process intervals sequentially and make local decisions. When examining two consecutive intervals, we only need to check if they overlap by comparing the end of the first interval with the start of the second interval. If end1 >= start2, they overlap and should be merged.

The merging process becomes straightforward: we maintain a "growing" interval that expands as we encounter overlapping intervals. When we find an interval that doesn't overlap with our current growing interval, we know we've found the boundary of a merged group, so we save the current merged interval and start a new one.

Why does sorting work? Without sorting, we'd need to compare every interval with every other interval to find all overlaps, which would be inefficient. Sorting transforms the problem from a global comparison issue to a local one - we only need to look at adjacent intervals. This is because if interval A comes before interval B after sorting (A's start ≤ B's start), and they don't overlap, then B cannot overlap with any interval that comes before A either.

The choice to update the end point using max(ed, e) handles cases where one interval completely contains another. For example, [1, 10] and [2, 5] - the second interval is fully contained within the first, so we keep the larger endpoint.

Learn more about Sorting patterns.

Solution Approach

The implementation follows a sorting and one-pass traversal strategy:

Step 1: Sort the intervals
We start by sorting the intervals array using intervals.sort(). This sorts intervals in ascending order by their first element (start point). After sorting, any intervals that could potentially overlap will be adjacent to each other.

Step 2: Initialize tracking variables
We create an empty result list ans to store merged intervals. We extract the first interval's start and end points into variables st and ed using st, ed = intervals[0]. These variables will track the current interval being built through merging.

Step 3: Traverse and merge
We iterate through the remaining intervals starting from index 1 using for s, e in intervals[1:]:

• Case 1: No overlap - If ed < s (current interval's end is less than next interval's start), the intervals don't overlap. We:

  • Append the completed interval [st, ed] to our answer
  • Start tracking a new interval by setting st, ed = s, e

• Case 2: Overlap exists - If ed >= s (current interval's end overlaps with or touches next interval's start), we:

  • Extend the current interval by updating ed = max(ed, e)
  • The max function handles cases where the current interval might completely contain the next one

Step 4: Add final interval
After the loop completes, we still have one last merged interval [st, ed] that hasn't been added to the result. We append it with ans.append([st, ed]).

Time Complexity: O(n log n) where n is the number of intervals - dominated by the sorting step. The traversal is O(n).

Space Complexity: O(1) if we don't count the output array, or O(n) if we do, where n is the number of intervals in the worst case (no overlaps).

Example Walkthrough

Let's walk through the solution with the input: intervals = [[1,3], [8,10], [2,6], [15,18]]

Step 1: Sort the intervals After sorting by start points: [[1,3], [2,6], [8,10], [15,18]]

Step 2: Initialize tracking variables

• ans = [] (empty result list)
• st = 1, ed = 3 (from first interval [1,3])

Step 3: Process each interval

Processing interval [2,6]:

• Check: Is ed < s? Is 3 < 2? No, so intervals overlap
• Update: ed = max(3, 6) = 6
• Current tracking: st = 1, ed = 6

Processing interval [8,10]:

• Check: Is ed < s? Is 6 < 8? Yes, no overlap
• Add completed interval [1,6] to result: ans = [[1,6]]
• Start new interval: st = 8, ed = 10

Processing interval [15,18]:

• Check: Is ed < s? Is 10 < 15? Yes, no overlap
• Add completed interval [8,10] to result: ans = [[1,6], [8,10]]
• Start new interval: st = 15, ed = 18

Step 4: Add final interval Add the last tracked interval [15,18] to result: ans = [[1,6], [8,10], [15,18]]

The algorithm successfully merged [1,3] and [2,6] into [1,6] while keeping the non-overlapping intervals [8,10] and [15,18] separate.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n × log n)

The time complexity is dominated by the sorting operation intervals.sort(), which takes O(n × log n) time where n is the number of intervals. After sorting, the code iterates through the intervals once in O(n) time to merge overlapping intervals. Since O(n × log n) + O(n) = O(n × log n), the overall time complexity is O(n × log n).

Space Complexity: O(log n)

The space complexity comes from the sorting algorithm. Python's built-in sort() uses Timsort, which requires O(log n) space for the recursion stack in the worst case. The output list ans stores the merged intervals, but this is not counted as extra space since it's the required output. The variables st and ed use constant O(1) space. Therefore, the overall space complexity is O(log n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Forgetting to handle edge cases with single interval or empty input

The current implementation assumes the input has at least one interval. If the input is empty, intervals[0] will throw an IndexError.

Solution: Add a guard clause at the beginning:

if not intervals:
    return []

2. Incorrect overlap condition

A frequent mistake is using current_end <= interval_start instead of current_end < interval_start for the non-overlap check. This would incorrectly treat touching intervals like [1, 3] and [3, 5] as non-overlapping, when they should merge into [1, 5].

Solution: Always use strict inequality current_end < interval_start to check for non-overlap. Intervals that share an endpoint should be merged.

3. Not using max() when merging intervals

When merging overlapping intervals, simply setting current_end = interval_end is incorrect. The current interval might completely contain the next interval (e.g., [1, 5] contains [2, 3]), so we need to keep the larger end value.

Solution: Always use current_end = max(current_end, interval_end) to ensure we keep the furthest-reaching endpoint.

4. Modifying the input array in-place

Sorting the input array with intervals.sort() modifies the original input. If the caller expects the input to remain unchanged, this creates a side effect.

Solution: Create a copy before sorting if input preservation is required:

intervals = sorted(intervals)  # Creates a new sorted list

5. Forgetting to add the last interval

After the loop completes, there's always one final merged interval that hasn't been added to the result. Forgetting merged_intervals.append([current_start, current_end]) after the loop will lose the last group of merged intervals.

Solution: Always remember to append the final interval after the loop, or restructure the logic to handle it within the loop by checking if it's the last iteration.