Introduction

The Merge Intervals problem involves combining overlapping intervals into a single interval.

Given:

  • an array of intervals

the task is to:

  • merge all overlapping intervals
  • return non-overlapping merged intervals

This problem is one of the most important applications of:

 Sorting + Interval Processing

This problem helps in understanding:

  • interval merging
  • sorting
  • greedy traversal
  • overlapping ranges

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 and merge into:
[1,6]

Constraints

1 <= intervals.length <= 10^50 <= start <= end <= 10^5

Approach 1 : Brute Force

Explanation

The simplest way to solve this problem is:

  1. Compare every interval
    with remaining intervals
  2. Merge overlapping intervals
  3. Repeat until no overlaps remain

This approach works but repeated comparisons increase complexity.

Steps

  1. Sort intervals.
  2. Compare intervals repeatedly.
  3. Merge overlaps.
  4. Continue traversal.
  5. Return merged intervals.

Dry Run

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

Compare:
[1,3] and [2,6]

Overlap exists

Merge:
[1,6]

Remaining intervals:
[[1,6],[8,10],[15,18]]
No further overlaps

Final Result:
[[1,6],[8,10],[15,18]]

Brute Force Code

Complexity Analysis

Time Complexity: O(n log n)Explanation:
Sorting dominates the complexity.

Space Complexity: O(n)
Explanation:
Extra merged array is used.

Approach 2 : Optimized Interval Merging

Explanation

The optimized solution uses:

 Sorting + Greedy Traversal

The idea is:

  1. Sort intervals by start time
  2. Compare with last merged interval
  3. Merge if overlap exists
  4. Otherwise add new interval

This avoids repeated comparisons.

Steps

  1. Sort intervals.
  2. Add first interval.
  3. Traverse remaining intervals.
  4. Merge overlaps.
  5. Add non-overlapping intervals.
  6. Return merged result.

Dry Run

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

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

Start with:
[1,3]

Compare with:
[2,6]

Overlap exists

Merge:
[1,6]



Compare with:
[8,10]

No overlap
Add interval

Final Result:
[[1,6],[8,10],[15,18]]

Optimized Interval Merging Code

Complexity Analysis

Time Complexity: O(n log n)Explanation:
Sorting dominates the complexity.

Space Complexity: O(n)
Explanation:
Merged intervals are stored separately.

Edge Cases

  1. Empty interval list
  2. Single interval
  3. Fully overlapping intervals
  4. Non-overlapping intervals
  5. Nested intervals

Why This Problem is Important

Merge Intervals helps in understanding:

  1. Sorting applications
  2. Interval merging
  3. Greedy traversal
  4. Overlapping range handling
  5. Array processing

It is one of the most important interval interview problems.

Real-World Applications

Interval merging concepts are used in:

  1. Calendar scheduling
  2. Meeting room systems
  3. Memory allocation
  4. CPU scheduling
  5. Booking systems

Common Mistakes

  1. Forgetting sorting step
  2. Incorrect overlap condition
  3. Wrong merge update
  4. Missing edge cases

Interview Tips

Interviewers often expect:

  1. Sorting explanation
  2. Greedy interval merging
  3. Overlap condition understanding

Always explain:

  • why sorting is necessary
  • how overlap is detected
  • why greedy merging works

Related Questions

  1. Insert Interval
  2. Meeting Rooms
  3. Non-overlapping Intervals
  4. Sort Colors
  5. Partition Array

Final Takeaway

The Merge Intervals problem is a fundamental interval-processing problem that teaches sorting and greedy merging techniques. Understanding this problem builds a strong foundation for advanced interval and scheduling interview problems.