Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

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.

Constraints

  • 1 <= intervals.length <= 10^4
  • intervals[i].length == 2
  • 0 <= starti <= endi <= 10^4

Thinking Process

  1. Sorting is crucial: Sort by start time to make overlapping intervals adjacent
  • Clarify if the array is sorted, has negatives, or allows duplicates.
  • Prefix sums answer range queries; hash maps answer pair/count queries.
  • In-place tricks use swap/write index instead of extra arrays.
Intervals on timeline sort by start → scan overlaps

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
Prefix sum (this problem) O(n) O(n) Range queries, subarray sum
Sort + scan O(n log n) O(1) Intervals, meeting rooms
Kadane’s algorithm O(n) O(1) Maximum subarray
Hash map counting O(n) O(n) Frequency, two-sum variants

Solution

Time Complexity: O(n log n) - dominated by sorting
Space Complexity: O(n) - for the merged result

The key insight is to sort intervals by start time, then merge overlapping intervals by comparing with the last merged interval.

Solution: Sort and Merge

class Solution:
    def merge(self, intervals):
        if len(intervals) == 0:
            return []

        intervals.sort()

        merged = []

        for i in range(len(intervals)):
            left = intervals[i][0]
            right = intervals[i][1]

            if not merged or merged[-1][1] < left:
                merged.append([left, right])
            else:
                merged[-1][1] = max(merged[-1][1], right)

        return merged

Solution Explanation

Approach: Prefix sum (this problem)

Key idea: 1. Sorting is crucial: Sort by start time to make overlapping intervals adjacent

How the code works:

  1. Sorting is crucial: Sort by start time to make overlapping intervals adjacent
    • Clarify if the array is sorted, has negatives, or allows duplicates.
    • Prefix sums answer range queries; hash maps answer pair/count queries.
    • In-place tricks use swap/write index instead of extra arrays.

Walkthrough — input intervals = [[1,3],[2,6],[8,10],[15,18]], expected output [[1,6],[8,10],[15,18]]:

Since intervals [1,3] and [2,6] overlap, merge them into [1,6].

| Approach | Time | Space | Pros | Cons | |———-|——|——-|——|——| | Sort and Merge | O(n log n) | O(n) | Simple, clear | Extra space | | Custom Comparator | O(n log n) | O(n) | Explicit | More verbose | | In-Place | O(n log n) | O(1) | Space efficient | Modifies input |

Algorithm Breakdown

Sorting

intervals.sort()

Why this works:

  • vector<vector<int>> sorts lexicographically
  • First compares intervals[i][0] (start time)
  • If equal, compares intervals[i][1] (end time)
  • This gives us intervals sorted by start time

Merging Logic

if len(merged) == 0  or  merged[-1][1] < left:
    merged.append(:left, right)
     else :
    merged[-1][1] = max(merged[-1][1], right)

Breakdown:

  • Empty merged list: First interval, add it
  • No overlap: merged.back()[1] < left means current interval starts after last ends
  • Overlap: merged.back()[1] >= left means intervals overlap, extend end time

Overlap Detection

Two intervals overlap if:

[a, b] and [c, d] overlap when: c <= b

Why c <= b?

  • If c <= b, the start of second interval is before/at the end of first
  • This means they overlap or are adjacent (which counts as overlap)

Examples:

  • [1,3] and [2,6]: 2 <= 3 → overlap ✓
  • [1,4] and [4,5]: 4 <= 4 → overlap ✓ (adjacent counts)
  • [1,3] and [4,6]: 4 <= 3 → no overlap ✗

Complexity

| Approach | Time | Space | Pros | Cons | |———-|——|——-|——|——| | Sort and Merge | O(n log n) | O(n) | Simple, clear | Extra space | | Custom Comparator | O(n log n) | O(n) | Explicit | More verbose | | In-Place | O(n log n) | O(1) | Space efficient | Modifies input |

Implementation Details

Why Lexicographic Sort Works

class Solution:
    def merge(self, intervals):
        if not intervals:
            return []

        intervals.sort(key=lambda x: x[0])

        merged = []
        merged.append(intervals[0])

        for i in range(1, len(intervals)):
            if intervals[i][0] <= merged[-1][1]:
                merged[-1][1] = max(merged[-1][1], intervals[i][1])
            else:
                merged.append(intervals[i])

        return merged

For vector<vector<int>>:

  • Compares first element (intervals[i][0])
  • If equal, compares second element (intervals[i][1])
  • This sorts by start time, then by end time if starts are equal

Example:

Before: [[2,6], [1,3], [8,10]]
After:  [[1,3], [2,6], [8,10]]

Overlap Condition Explained

class Solution:
    def merge(self, intervals):
        if not intervals:
            return []

        intervals.sort()
        writeIdx = 0

        for i in range(1, len(intervals)):
            if intervals[i][0] <= intervals[writeIdx][1]:
                intervals[writeIdx][1] = max(intervals[writeIdx][1], intervals[i][1])
            else:
                writeIdx += 1
                intervals[writeIdx] = intervals[i]

        intervals = intervals[:writeIdx + 1]
        return intervals

Why this works:

  • merged.back()[1] is the end time of last merged interval
  • left is the start time of current interval
  • If end < start, there’s a gap → no overlap
  • If end >= start, they overlap or are adjacent

Merge Operation

intervals.sort()

Why max?

  • When merging [a,b] and [c,d] where c <= b
  • New interval is [a, max(b,d)]
  • We keep the earlier start (a) and later end (max(b,d))

Common Mistakes

  1. Empty input: Return empty array
  2. Single interval: Return as-is
  3. All intervals overlap: Merge into one interval
  4. No overlaps: Return all intervals unchanged
  5. Adjacent intervals: [1,4] and [4,5] merge to [1,5]

  6. Nested intervals: [1,6] and [2,4] merge to [1,6]

  7. Forgetting to sort: Without sorting, algorithm fails
  8. Wrong overlap condition: Using >= instead of <= or vice versa
  9. Not handling empty input: Forgetting edge case
  10. Wrong merge logic: Not using max() for end time
  11. Index out of bounds: Not checking merged.size() == 0

Optimization Tips

  1. Early return: Check empty input first
  2. Reserve space: Can reserve intervals.size() for merged if needed
  3. In-place if allowed: Use in-place approach to save space

Real-World Applications

  1. Calendar Scheduling: Merging overlapping time slots
  2. Resource Allocation: Combining overlapping resource reservations
  3. Network Routing: Merging overlapping IP ranges
  4. Database Queries: Optimizing range queries
  5. Event Management: Consolidating overlapping events

Pattern Recognition

This problem demonstrates the “Interval Merging” pattern:

1. Sort intervals by start time
2. Iterate through sorted intervals
3. Compare current with last merged interval
4. If overlap → merge by extending end time
5. If no overlap → add as new interval

Similar problems:

  • Insert Interval
  • Meeting Rooms
  • Non-overlapping Intervals
  • Car Pooling

Step-by-Step Trace: intervals = [[1,4],[0,4]]

Step 1: Sort intervals
  Before: [[1,4], [0,4]]
  After:  [[0,4], [1,4]]  (sorted by start time)

Step 2: Initialize
  merged = []

Step 3: Process [0,4]
  merged is empty → add [0,4]
  merged = [[0,4]]

Step 4: Process [1,4]
  Check: merged.back()[1] = 4, current left = 1
  Since 4 >= 1, intervals overlap → merge
  merged.back()[1] = max(4, 4) = 4
  merged = [[0,4]]

Final: [[0,4]]

Why Sorting is Essential

Without sorting:

Input: [[2,6], [1,3], [8,10]]
Process [2,6]: merged = [[2,6]]
Process [1,3]: Check 6 < 1? No, but [1,3] should merge with [2,6]!
               Algorithm fails because [1,3] comes after [2,6]

With sorting:

Input: [[1,3], [2,6], [8,10]]
Process [1,3]: merged = [[1,3]]
Process [2,6]: Check 3 >= 2? Yes → merge → [[1,6]]
Process [8,10]: Check 6 < 8? Yes → add → [[1,6], [8,10]]

Interval Overlap Visualization

No Overlap:
  [a---b]        [c---d]
  └─ gap ─┘

Overlap:
  [a---b]
      [c---d]
  └─ overlap ─┘

Adjacent (counts as overlap):
  [a---b][c---d]
  └─ adjacent ─┘

Nested:
  [a--------b]
    [c---d]
  └─ nested ─┘

Follow-Up: Merge Intervals from Two Arrays

Problem: Given two arrays of intervals arr1 and arr2, merge all intervals from both arrays into one merged array.

Example:

Input: 
  arr1 = [[1,3],[2,6],[8,10]]
  arr2 = [[2,4],[7,9],[15,18]]

Output: [[1,6],[7,10],[15,18]]
Explanation: 
  - [1,3] and [2,6] from arr1 merge to [1,6]
  - [2,4] from arr2 overlaps with [1,6] → merge to [1,6]
  - [8,10] from arr1 and [7,9] from arr2 merge to [7,10]
  - [15,18] from arr2 is separate

Solution: Combine, Sort, and Merge

Time Complexity: O((m+n) log(m+n)) where m and n are sizes of arr1 and arr2
Space Complexity: O(m+n)

The key insight is to combine both arrays, sort all intervals together, then apply the standard merge algorithm.

merged[-1][1] < left  # No overlap
merged[-1][1] >= left # Overlap

Alternative: More Efficient Approach

Time Complexity: O(m log m + n log n + m + n)
Space Complexity: O(m + n)

First merge each array individually, then merge the two merged arrays using two pointers.

merged[-1][1] = max(merged[-1][1], right)

How the Two-Pointer Approach Works

Step-by-Step Example:

arr1 (merged): [[1,6], [8,10]]
arr2 (merged): [[2,4], [7,9], [15,18]]

Step 1: Compare [1,6] and [2,4]
  Choose [1,6] (smaller start)
  result = [[1,6]]

Step 2: Compare [8,10] and [2,4]
  Choose [2,4] (smaller start)
  Check: 6 >= 2 → overlap → merge
  result.back()[1] = max(6, 4) = 6
  result = [[1,6]]

Step 3: Compare [8,10] and [7,9]
  Choose [7,9] (smaller start)
  Check: 6 < 7 → no overlap → add
  result = [[1,6], [7,9]]

Step 4: Compare [8,10] and [15,18]
  Choose [8,10] (smaller start)
  Check: 9 >= 8 → overlap → merge
  result.back()[1] = max(9, 10) = 10
  result = [[1,6], [7,10]]

Step 5: Only [15,18] remains
  Add [15,18]
  result = [[1,6], [7,10], [15,18]]

Complexity Comparison

Approach Time Complexity Space Complexity Pros Cons
Combine & Sort O((m+n) log(m+n)) O(m+n) Simple, straightforward Sorts all intervals together
Two-Pointer Merge O(m log m + n log n + m + n) O(m+n) More efficient if arrays are pre-sorted More complex implementation

When to use each:

  • Combine & Sort: Simpler code, good when arrays are small or unsorted
  • Two-Pointer: More efficient when arrays are already sorted or large

Key Insights for Follow-Up

  1. Combine first: Merge both arrays before sorting
  2. Same merge logic: After combining, use the same overlap detection
  3. Two-pointer optimization: Can merge two already-merged arrays efficiently
  4. Pre-sorting benefit: If arrays are pre-sorted, two-pointer is optimal

This problem is a classic interval merging problem that demonstrates the importance of sorting and efficient overlap detection.

Key Takeaways

  1. Sorting is crucial: Sort by start time to make overlapping intervals adjacent
  2. Compare with last merged: Only need to check overlap with the last interval in merged list
  3. Overlap condition: Two intervals [a,b] and [c,d] overlap if c <= b
  4. Merge by extending: When overlapping, extend end time to max(b, d)

References

Template Reference