Introduction

Merge Intervals is one of the most important interval problems.

You are given:

  • A collection of intervals

Goal:

Merge all overlapping intervals and return the resulting intervals.

Example

Input

 intervals = [[1,3],[2,6],[8,10],[15,18]]

Output

[[1,6],[8,10],[15,18]]

Explanation

[1,3] and [2,6] overlap.
They are merged into [1,6].

Key Observation

If intervals are sorted by start time, overlapping intervals will appear next to each other.

Algorithm

  1. Sort intervals by start value.
  2. Add first interval to answer.
  3. Iterate through remaining intervals.
  4. If current interval overlaps:
    • Merge intervals.
  5. Otherwise:
    • Add new interval.
  6. Return result.

Dry Run

Input

[[1,3],[2,6],[8,10],[15,18]]

Sort

[[1,3],[2,6],[8,10],[15,18]]

Compare

[1,3] and [2,6]
Overlap Found
Merge
[1,6]
Next Interval
[8,10]
No Overlap
Next Interval
[15,18]
No Overlap

Answer

[[1,6],[8,10],[15,18]]

Approach : Greedy + Sorting

Sort intervals by start value.

If the current interval overlaps with the last merged interval, extend the end point.

Otherwise create a new interval.

Practice

Complexity Analysis

Time Complexity: O(n log n)Explanation: Sorting the intervals dominates the running time. The merging pass takes O(n).

Space Complexity: O(n)
Explanation: The result array may store all intervals in the worst case when no intervals overlap.

Why This Problem is Important

Merge Intervals introduces interval processing, sorting-based greedy strategies, and forms the foundation for many scheduling and interval problems.

Common Beginner Mistakes

  • Forgetting to sort intervals.
  • Comparing with wrong interval.
  • Updating start instead of end.
  • Missing complete overlap cases.

Interview Tip

Always mention:

After sorting, overlapping intervals become adjacent, making them easy to merge in one pass.

Related Questions

  • Insert Interval
  • Non-overlapping Intervals
  • Meeting Rooms
  • Meeting Rooms II
  • Employee Free Time

Final Takeaway

Merge Intervals is a classic interval greedy problem. The key insight is to sort intervals first and then merge overlapping intervals while traversing the array once. This pattern appears frequently in interview questions involving scheduling and ranges.