299. Merge Intervals

🔗 LeetCode Problem: 56. Merge Intervals
📊 Difficulty: Medium
🏷️ Topics: Array, Sorting

Problem Statement

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.

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

---

🌳 Visual Understanding - The Merge Problem

The Problem We're Solving:

Intervals on timeline:

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

Overlaps:
  [1,3] and [2,6] overlap → merge into [1,6]
  [8,10] standalone
  [15,18] standalone

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

Understanding When to Merge:

Two intervals should be merged if they OVERLAP or TOUCH

Interval A: [start_A, end_A]
Interval B: [start_B, end_B]

Assume sorted by start: start_A ≤ start_B

They overlap/touch if:
  end_A >= start_B

Examples:
  [1,3] and [2,6]: 3 >= 2 → MERGE to [1,6]
  [1,4] and [4,5]: 4 >= 4 → MERGE to [1,5] (touching!)
  [1,3] and [5,7]: 3 >= 5? NO → Keep separate

Important: This problem treats TOUCHING as overlapping!
  [1,4] and [4,5] merge to [1,5]

Key Observations:

1. Overlapping intervals should merge
   [1,3] + [2,6] → [1,6]

2. Touching intervals should merge
   [1,4] + [4,5] → [1,5]

3. Non-overlapping intervals stay separate
   [1,3] and [5,7] → [1,3], [5,7]

4. Merged interval spans both:
   start = min(start_A, start_B)
   end = max(end_A, end_B)

5. Need to handle CHAINS of overlaps:
   [1,3], [2,5], [4,7] → All merge to [1,7]!

---

🧠 The AHA Moment - Sort First, Then Merge

Approach 1: Brute Force (For Understanding)

Check all pairs for overlaps:
  For each interval:
    Check if it overlaps with any other interval
    If yes, merge them
    Repeat until no more merges possible

Problems:
  - Need multiple passes (chains of overlaps)
  - Hard to know when done
  - Time: O(n²) or worse!

This is messy! There must be a better way! 🤔

The Key Insight - Sort by Start Time

If we SORT intervals by start time:
  - Process them in chronological order
  - Can merge with PREVIOUS interval as we go
  - Single pass through sorted array!
  - Much cleaner logic!

Algorithm:
  1. Sort by start time
  2. Start with first interval
  3. For each next interval:
     - Does it overlap with current merged interval?
     - YES → Extend the current interval
     - NO → Add current to result, start new interval
  4. Don't forget to add the last interval!

This is O(n log n) for sorting + O(n) for merging = O(n log n)! 🎯

Visual Discovery:

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

Already sorted by start time!

Step-by-step merging:

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Initialize with first interval
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

current = [1, 3]
result = []

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Process [2, 6]
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

current = [1, 3]
next = [2, 6]

Check: 3 >= 2? YES! They overlap!

Merge: current = [1, max(3, 6)] = [1, 6]
       Keep as current, don't add to result yet

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Process [8, 10]
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

current = [1, 6]
next = [8, 10]

Check: 6 >= 8? NO! They don't overlap!

Action:
  Add current [1,6] to result
  Start new current = [8, 10]

result = [[1, 6]]

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Process [15, 18]
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

current = [8, 10]
next = [15, 18]

Check: 10 >= 15? NO! They don't overlap!

Action:
  Add current [8,10] to result
  Start new current = [15, 18]

result = [[1,6], [8,10]]

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Finish - Add last interval
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Add current [15,18] to result

result = [[1,6], [8,10], [15,18]] ✓

---

🔴 Approach 1: Brute Force (For Understanding)

💡 Intuition

Keep checking pairs and merging until no more overlaps

Algorithm:
  1. Create a merged list starting with all intervals
  2. Repeatedly scan for overlapping pairs
  3. When found, merge them and start over
  4. Stop when no overlaps found

This helps understand the problem but is too slow!

📊 Complexity Analysis

Time Complexity: O(n³) or worse

Multiple passes: O(n)
Each pass checks all pairs: O(n²)
Total: O(n²) to O(n³)

Way too slow for large inputs!

Why we won't implement this: - Too slow and complex - Sorting approach is much better - Good to understand the naive approach conceptually

---

🟢 Approach 2: Sort and Merge (Optimal)

🎨 Building the Complete Solution

Step 1: Sort by Start Time

Sort intervals by start time (ascending)

Why?
  - Process intervals chronologically
  - Can merge with previous interval linearly
  - Single pass through array!

Step 2: Initialize with First Interval

Start building merged intervals:
  current = first interval
  result = []

We'll grow 'current' as we merge overlapping intervals

Step 3: Process Each Interval

For each interval (starting from second):

  If overlaps with current:
    Merge: current.end = max(current.end, interval.end)
    Continue (keep current growing)

  Else (no overlap):
    Add current to result
    Start new: current = this interval

Step 4: Add Last Interval

After loop, don't forget to add the last 'current' interval!

This is a common mistake!

📝 Implementation - Clean and Clear

import java.util.*;

class Solution {
    public int[][] merge(int[][] intervals) {
        // Edge case
        if (intervals.length <= 1) {
            return intervals;
        }

        // Step 1: Sort by start time
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);

        // Step 2: Initialize result list
        List<int[]> merged = new ArrayList<>();

        // Step 3: Start with first interval
        int[] current = intervals[0];

        // Step 4: Process each interval
        for (int i = 1; i < intervals.length; i++) {
            int[] interval = intervals[i];

            // Check if current interval overlaps with next
            if (current[1] >= interval[0]) {
                // Overlap! Merge by extending current
                current[1] = Math.max(current[1], interval[1]);
            } else {
                // No overlap! Add current to result, start new
                merged.add(current);
                current = interval;
            }
        }

        // Step 5: Don't forget to add the last interval!
        merged.add(current);

        // Convert list to array
        return merged.toArray(new int[merged.size()][]);
    }
}

🔍 Complete Dry Run - Example 1

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

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
STEP 1: Sort by start time
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

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

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
STEP 2: Initialize
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

current = [1, 3]
merged = []

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
STEP 3: Process intervals
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

i=1: interval = [2, 6]
  Check: current[1] >= interval[0]?
         3 >= 2? YES! Overlap!

  Merge: current[1] = max(3, 6) = 6
  current = [1, 6]

  merged = [] (nothing added yet)

i=2: interval = [8, 10]
  Check: current[1] >= interval[0]?
         6 >= 8? NO! No overlap!

  Action:
    Add current [1,6] to merged
    Start new: current = [8, 10]

  merged = [[1,6]]

i=3: interval = [15, 18]
  Check: current[1] >= interval[0]?
         10 >= 15? NO! No overlap!

  Action:
    Add current [8,10] to merged
    Start new: current = [15, 18]

  merged = [[1,6], [8,10]]

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
STEP 4: Add last interval
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Add current [15,18] to merged

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

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
RESULT
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Return: [[1,6], [8,10], [15,18]] ✓

Complete Dry Run - Example 2 (Touching Intervals)

Input: intervals = [[1,4],[4,5]]

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
SORT
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Already sorted: [[1,4],[4,5]]

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
INITIALIZE
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

current = [1, 4]
merged = []

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
PROCESS
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

i=1: interval = [4, 5]
  Check: current[1] >= interval[0]?
         4 >= 4? YES! They touch!

  Merge: current[1] = max(4, 5) = 5
  current = [1, 5]

  merged = []

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
ADD LAST
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Add current [1,5] to merged

merged = [[1,5]]

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
RESULT
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Return: [[1,5]] ✓

Note: Touching intervals [1,4] and [4,5] merged!
This is DIFFERENT from Meeting Rooms where touching was OK!

Complex Example - Chain of Overlaps

Input: intervals = [[1,4],[2,5],[4,6],[7,8],[8,10]]

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
PROCESS
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

current = [1, 4]

Process [2,5]:
  4 >= 2? YES → Merge
  current = [1, 5]

Process [4,6]:
  5 >= 4? YES → Merge
  current = [1, 6]

Process [7,8]:
  6 >= 7? NO → No overlap
  Add [1,6] to result
  current = [7, 8]

Process [8,10]:
  8 >= 8? YES → Merge (touching!)
  current = [7, 10]

Add last [7,10] to result

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
RESULT
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

[[1,6], [7,10]] ✓

Three intervals [1,4], [2,5], [4,6] merged into [1,6]!
Two intervals [7,8], [8,10] merged into [7,10]!

📊 Complexity Analysis

Time Complexity: O(n log n)

Sorting: O(n log n)
Single pass merge: O(n)
Total: O(n log n)

Dominated by sorting!
OPTIMAL for comparison-based approach!

Space Complexity: O(n)

Result list: O(n) in worst case (no merges)
Sorting space: O(log n) recursion stack

If output space doesn't count: O(log n)

---

🎯 Key Insights Summary

The Three Critical Points:

1. Sort by Start Time

Sorting enables linear merging!

Benefits:
  - Process chronologically
  - Only check with previous interval
  - Single pass through array

This is THE key optimization! 🔑

2. Merge Condition

Two consecutive sorted intervals merge if:
  current.end >= next.start

Important: >= not >
  Touching intervals merge in this problem!
  [1,4] and [4,5] → [1,5]

Different from Meeting Rooms!

3. Extend End When Merging

When merging:
  Keep current.start (already minimum)
  Update: current.end = max(current.end, next.end)

Why max?
  next might be completely inside current!
  [1,10] and [2,5] → [1,10] not [1,5]!

---

💡 Why This Approach Works - Deep Intuition

The Sorting Magic

Why does sorting by start time enable linear merging?

After sorting:
  [A, B, C, D, ...]
  where start_A ≤ start_B ≤ start_C ≤ ...

Key Property:
  If A doesn't overlap with B (next),
  then A is DONE merging!
  A won't overlap with C, D, ... either!

Why?
  Because C, D... start even later than B!
  If A.end < B.start
  Then A.end < C.start, D.start, ...

Therefore: Process once, left to right! ✓

Why We Need max() When Merging

Example:
  current = [1, 10]
  next = [2, 5]

Without max():
  Merge: current = [1, 5] ✗ WRONG!

With max():
  Merge: current = [1, max(10, 5)] = [1, 10] ✓ CORRECT!

The next interval might be completely INSIDE current!
Always take the maximum end point!

---

⚠️ Common Mistakes

// Mistake 1: Forgetting to add last interval
for (int i = 1; i < intervals.length; i++) {
    // ... merge logic
}
// ❌ Forgot: merged.add(current);
// ✓ CORRECT: Always add last interval after loop!
merged.add(current);

// Mistake 2: Wrong merge condition
if (current[1] > interval[0]) { // ❌ Should be >=
// ✓ CORRECT: >= to handle touching
if (current[1] >= interval[0]) {

// Mistake 3: Not using max when merging
current[1] = interval[1]; // ❌ Wrong if interval inside current!
// ✓ CORRECT:
current[1] = Math.max(current[1], interval[1]);

// Mistake 4: Creating new array instead of extending
current = new int[]{current[0], interval[1]}; // ❌ Unnecessary
// ✓ CORRECT: Just update end
current[1] = Math.max(current[1], interval[1]);

// Mistake 5: Not handling edge case
// ❌ No edge case check
// ✓ CORRECT:
if (intervals.length <= 1) return intervals;

---

🎓 Comparison with Meeting Rooms

┌────────────────────────┬──────────────────┬──────────────────┐
│ Aspect                 │ Meeting Rooms    │ Merge Intervals  │
├────────────────────────┼──────────────────┼──────────────────┤
│ Goal                   │ Can attend all?  │ Merge overlaps   │
│ Touching intervals     │ OK (don't merge) │ Merge them!      │
│ Condition              │ end > next_start │ end >= next_start│
│ Output                 │ boolean          │ merged intervals │
│ Complexity             │ O(n log n)       │ O(n log n)       │
└────────────────────────┴──────────────────┴──────────────────┘

KEY DIFFERENCE: Treatment of touching intervals!
  Meeting Rooms: [1,4] and [4,5] → separate (can attend both)
  Merge Intervals: [1,4] and [4,5] → [1,5] (merge them)

---

📝 Quick Revision Notes

🎯 Core Concept

Problem: Merge all overlapping intervals

Key Insight: Sort by start time, then merge linearly!

Algorithm: 1. Sort intervals by start time 2. Start with first interval as current 3. For each next interval: - If overlaps (current.end >= next.start): merge - Else: add current to result, start new 4. Add last interval to result

Why It Works: After sorting, can process left to right in single pass!

⚡ Quick Implementation

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution {
  public int[][] merge(int[][] a) {
    // step 1: sort by start time
    Arrays.sort(a, (m1, m2) -> m1[0] - m2[0]);

    // step 2: go through all meetings
    List<int[]> list = new ArrayList<>();
    list.add(new int[] { a[0][0], a[0][1] });

    for (int i = 1; i < a.length; i++) {
      int[] prev = list.get(list.size() - 1);
      int[] curr = a[i];

      if (curr[0] >= prev[0] && curr[0] <= prev[1]) {
        // if curr meeting falls in between prev meeting, include it.
        int max = Math.max(prev[1], curr[1]);
        list.remove(list.size() - 1);
        list.add(new int[] { prev[0], max });
      } else {
        // else add it as a new entry
        list.add(curr);
      }
    }

    // step 3: convert this list to array
    int size = list.size();
    int[][] res = new int[size][2];
    for (int i = 0; i < size; i++) {
      res[i][0] = list.get(i)[0];
      res[i][1] = list.get(i)[1];
    }

    return res;
  }

  public static void main(String[] args) {
    Solution s = new Solution();

    // [[1,6],[8,10],[15,18]]
    System.out.println(Arrays.deepToString(s.merge(new int[][] { { 1, 3 }, { 2, 6 }, { 8, 10 }, { 15, 18 } })));
    // [[1,5]]
    System.out.println(Arrays.deepToString(s.merge(new int[][] { { 1, 4 }, { 4, 5 } })));
    // [[1,7]]
    System.out.println(Arrays.deepToString(s.merge(new int[][] { { 4, 7 }, { 1, 4 } })));
  }
}

🔑 Key Points

✓ Sort by start time: O(n log n)
✓ Merge condition: end >= next_start (>= not >!)
✓ When merging: use max(current.end, next.end)
✓ Don't forget to add last interval!
✓ Touching intervals merge (different from Meeting Rooms)
✓ Time: O(n log n), Space: O(n)

🎪 Memory Aid

"Sort by start, don't restart!"
"Check with last, merge them fast!"
"End >= start? Don't keep apart!"
"Max of ends, the merge extends!" ✨

---

🎉 Congratulations!

You've mastered Merge Intervals!

What You Learned:

✅ Interval merging - Core technique
✅ Sort + linear scan - O(n log n) pattern
✅ Merge condition - end >= next_start
✅ Max when merging - Handle nested intervals
✅ Edge cases - Last interval, touching intervals

The Beautiful Insight:

Interval Merging → Sort + Linear Scan

The core insight:
  "Unsorted intervals → Hard to merge"
  "Sorted intervals → Easy linear merge"

  Why sorting helps:
    - Chronological order
    - Only check with previous interval
    - Can finish current before moving to next

  Single pass after sorting!

This pattern appears in MANY problems:
  - Insert interval
  - Interval list intersections
  - Employee free time
  - Calendar problems

Master this pattern = Solve many problems! ✨

Interview Mastery:

When asked about Merge Intervals:

1. Understand: "Merge all overlapping intervals"

2. Clarify: "Do touching intervals merge?
   [1,4] and [4,5] → [1,5]? (YES in this problem!)"

3. Brute force: "Could check all pairs repeatedly - O(n²) or worse"

4. Key insight: "Sort by start time first!
   Then can merge linearly in one pass."

5. Merge condition: "current.end >= next.start
   Use >= to handle touching intervals."

6. Handle nested: "Use max(current.end, next.end) when merging"

7. Don't forget: "Add the last interval after loop!"

8. Code it: Clean O(n log n) solution

9. Complexity: "O(n log n) for sorting, O(n) for merging.
   O(n) space for result."

Shows complete understanding! 💯

You've mastered a fundamental interval problem! This merging technique is used in countless real-world applications! 🚀✨🎯