292. Non-overlapping Intervals

🔗 LeetCode Problem: 435. Non-overlapping Intervals
📊 Difficulty: Medium
🏷️ Topics: Array, Greedy, Sorting, Dynamic Programming

Problem Statement

Given an array of intervals intervals where intervals[i] = [starti, endi], return the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.

Example 1:

Input: intervals = [[1,2],[2,3],[3,4],[1,3]]
Output: 1
Explanation: [1,3] can be removed and the rest of the intervals are non-overlapping.

Example 2:

Input: intervals = [[1,2],[1,2],[1,2]]
Output: 2
Explanation: You need to remove two [1,2] to make the rest of the intervals non-overlapping.

Example 3:

Input: intervals = [[1,2],[2,3]]
Output: 0
Explanation: You don't need to remove any of the intervals since they're already non-overlapping.

Constraints: - 1 <= intervals.length <= 10^5 - intervals[i].length == 2 - -5 * 10^4 <= starti < endi <= 5 * 10^4

---

🌳 Visual Understanding - The Overlapping Intervals Problem

The Problem We're Solving:

Intervals on a timeline:

    [1, 2]     [2, 3]     [3, 4]
    |---|      |---|      |---|
    1   2      2   3      3   4

Question: Are these overlapping?

[1,2] and [2,3]: Touch at point 2 but DON'T overlap
[2,3] and [3,4]: Touch at point 3 but DON'T overlap

Result: NO overlaps! Remove 0 intervals.

Understanding Overlaps:

What IS an overlap?

Overlap Example 1:
    [1,   3]
    |-----|
      [2,   4]
      |-----|

    Overlap region: [2, 3]
    These intervals OVERLAP! ✗

Overlap Example 2:
    [1,     4]
    |-------|
      [2, 3]
      |---|

    [2,3] is completely inside [1,4]
    These intervals OVERLAP! ✗

Non-overlap Example:
    [1, 2]     [2, 3]
    |---|      |---|

    They touch at point 2 but DON'T overlap
    Non-overlapping! ✓

Key Rule:
  Intervals [a,b] and [c,d] overlap if:
    a < d AND c < b

  They DON'T overlap if:
    b <= c  (first ends before or when second starts)
    OR
    d <= a  (second ends before or when first starts)

The Problem with Example 1:

Input: [[1,2], [2,3], [3,4], [1,3]]

Visualize on timeline:

    [1, 2]
    |---|
          [2, 3]
          |---|
                [3, 4]
                |---|
    [1,     3]
    |-------|

Which overlap?
  [1,2] and [2,3]: Touch at 2, don't overlap ✓
  [2,3] and [3,4]: Touch at 3, don't overlap ✓
  [1,3] and [2,3]: 1 < 3 AND 2 < 3 → OVERLAP! ✗
  [1,3] and [1,2]: 1 < 2 AND 1 < 3 → OVERLAP! ✗
  [1,3] and [3,4]: Touch at 3, don't overlap ✓

[1,3] overlaps with both [1,2] and [2,3]!
Remove [1,3] → All others are non-overlapping!

Answer: Remove 1 interval

Key Observations:

1. Touching is OK
   [1,2] and [2,3] can coexist (touch at 2)

2. Overlapping is NOT OK
   [1,3] and [2,3] cannot coexist (overlap at [2,3])

3. We want MINIMUM removals
   Remove as few as possible
   Keep as many as possible!

4. Think inversely:
   "Minimum removals" = Total - "Maximum non-overlapping"
   If we can keep k intervals, we remove (n - k)

---

🧠 The AHA Moment - Greedy Strategy

The Brute Force Nightmare:

Try all possible combinations:
  - Which intervals to keep?
  - Which to remove?
  - 2^n possibilities for n intervals!

This is O(2^n) - IMPOSSIBLE for large n! 😰

The Key Insight - Activity Selection Problem

This is a classic "Activity Selection" problem!

Think about it differently:
  Instead of "which to remove?"
  Ask: "What's the MAXIMUM number we can keep?"

Answer: Remove = Total - Maximum_kept

How to maximize intervals kept?
  Greedy strategy: Pick intervals that END EARLY!

Why? Early-ending intervals leave MORE ROOM for others!

Visual Discovery - Why "End Early" Works

Scenario 1: Pick the interval that ends LATE
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Intervals:
    [1,        5]  ← Ends late
    |----------|
      [2, 3]
      |---|
         [3, 4]
         |---|

If we pick [1,5]:
  - It overlaps with [2,3] and [3,4]
  - We can only keep [1,5]
  - Total kept: 1

Scenario 2: Pick the interval that ends EARLY
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Intervals:
    [1,        5]
    |----------|
      [2, 3]  ← Ends early!
      |---|
         [3, 4]
         |---|

If we pick [2,3]:
  - We can still pick [3,4] after (they don't overlap)
  - We can still pick [1,5]? No, overlaps with [2,3]
  - But we can pick [2,3] and [3,4]
  - Total kept: 2 ✓ BETTER!

INSIGHT: Pick intervals that end early!
         They leave more room for future intervals! 🎯

The Greedy Strategy

Algorithm:
1. Sort intervals by END time (ascending)
2. Greedily pick intervals:
   - Pick first interval (ends earliest)
   - Pick next interval that doesn't overlap with last picked
   - Repeat
3. Count how many we picked
4. Answer = Total - Picked

Why this is optimal:
  By picking earliest-ending intervals:
  - We maximize available space for future intervals
  - We can fit MORE intervals
  - This gives MINIMUM removals!

Detailed Example - Understanding the Greedy Choice

Input: [[1,2], [2,3], [3,4], [1,3]]

Step 1: Sort by end time
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Original: [[1,2], [2,3], [3,4], [1,3]]
           end=2   end=3   end=4   end=3

After sorting by end:
[[1,2], [2,3], [1,3], [3,4]]
 end=2   end=3   end=3   end=4

Step 2: Greedily pick non-overlapping intervals
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

lastEnd = -infinity (initially)
count = 0

Process [1,2]: start=1, end=2
  Does 1 >= lastEnd (-∞)? YES! (no overlap)
  Pick this interval ✓
  lastEnd = 2
  count = 1

Process [2,3]: start=2, end=3
  Does 2 >= lastEnd (2)? YES! (no overlap, they touch)
  Pick this interval ✓
  lastEnd = 3
  count = 2

Process [1,3]: start=1, end=3
  Does 1 >= lastEnd (3)? NO! (1 < 3, overlaps!)
  Skip this interval ✗
  lastEnd = 3
  count = 2

Process [3,4]: start=3, end=4
  Does 3 >= lastEnd (3)? YES! (no overlap, they touch)
  Pick this interval ✓
  lastEnd = 4
  count = 3

Step 3: Calculate removals
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Total intervals: 4
Intervals kept: 3
Intervals removed: 4 - 3 = 1 ✓

Kept: [1,2], [2,3], [3,4]
Removed: [1,3]

Visual verification:
  [1,2]     [2,3]     [3,4]
  |---|     |---|     |---|

  No overlaps! ✓

---

🔴 Approach 1: Brute Force (For Understanding Only)

💡 Intuition

"Try all possible subsets and check if non-overlapping"

For each subset of intervals:
  Check if all intervals in subset are non-overlapping
  Track maximum size of non-overlapping subset

Answer = Total - Maximum_subset_size

Too slow but helps understand the problem!

📊 Complexity Analysis

Time Complexity: O(2^n × n²)

Generate all subsets: O(2^n)
Check each subset: O(n²)
Total: O(2^n × n²)

Way too slow! ⚠️

---

🟡 Approach 2: Dynamic Programming

📐 DP Definition

dp[i] = maximum number of non-overlapping intervals 
        we can select from first i intervals (after sorting)

Base case: dp[0] = 1 (first interval always selected)

Transition:
  For each interval i:
    Option 1: Don't take interval i
      dp[i] = dp[i-1]

    Option 2: Take interval i
      Find last interval j that doesn't overlap with i
      dp[i] = dp[j] + 1

    dp[i] = max(Option 1, Option 2)

📝 Implementation

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        if (intervals.length == 0) return 0;

        // Sort by end time
        Arrays.sort(intervals, (a, b) -> a[1] - b[1]);

        int n = intervals.length;
        int[] dp = new int[n];
        dp[0] = 1;  // Base case

        for (int i = 1; i < n; i++) {
            // Option 1: Don't take interval i
            dp[i] = dp[i - 1];

            // Option 2: Take interval i
            // Find last non-overlapping interval
            for (int j = i - 1; j >= 0; j--) {
                if (intervals[j][1] <= intervals[i][0]) {
                    // Found non-overlapping interval
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                    break;
                }
            }

            // If no previous interval found (all overlap)
            if (dp[i] == dp[i - 1]) {
                dp[i] = Math.max(dp[i], 1);
            }
        }

        // Maximum intervals we can keep
        int maxKeep = dp[n - 1];

        // Minimum to remove
        return n - maxKeep;
    }
}

📊 Complexity Analysis

Time Complexity: O(n²)

Sorting: O(n log n)
DP with nested loop: O(n²)
Total: O(n²)

Space Complexity: O(n)

DP array: O(n)

---

🟢 Approach 3: Greedy (Optimal)

🎨 Building Deep Intuition - Step by Step

Let me show you WHY the greedy approach works with detailed reasoning:

Step 1: Why Sort by End Time?

Question: Should we sort by START time or END time?

Let's compare:

Example intervals:
    [1,      10]
    |--------|
      [2, 3]
      |---|
         [4, 5]
         |---|

Scenario A: Sort by START time
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

After sorting: [[1,10], [2,3], [4,5]]

Greedy pick first: [1,10]
  - [2,3] overlaps with [1,10] → skip
  - [4,5] overlaps with [1,10] → skip

Result: Keep only 1 interval ✗

Scenario B: Sort by END time
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

After sorting: [[2,3], [4,5], [1,10]]
               end=3   end=5   end=10

Greedy pick first: [2,3]
  - [4,5]: start=4 >= 3 (end of [2,3]) → Pick! ✓
  - [1,10]: start=1 < 5 (overlaps) → skip

Result: Keep 2 intervals ✓ BETTER!

CONCLUSION: Sort by END time!
  Intervals that end early leave more room for others!

Step 2: The Greedy Choice - Pick Earliest Ending

Why pick the interval that ends earliest?

Think of it like scheduling meetings:
  - You have limited time (the timeline)
  - You want to fit MAXIMUM meetings
  - Pick meetings that END EARLY
  - This frees up time for MORE meetings later!

Mathematical reasoning:
  If we have two intervals A and B where:
    - A ends earlier than B
    - Both are valid choices (don't overlap with previous)

  Choosing A is ALWAYS at least as good as choosing B:
    - A ends earlier → leaves more room
    - Any interval compatible with B is also compatible with A
    - But some intervals compatible with A might not be compatible with B

  Therefore: Always pick the earliest ending! 🎯

Step 3: Detailed Example with Complete Reasoning

Input: [[1,2], [2,3], [3,4], [1,3]]

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
STEP 1: Sort by end time
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Before: [[1,2], [2,3], [3,4], [1,3]]
After:  [[1,2], [2,3], [1,3], [3,4]]
         end=2   end=3   end=3   end=4

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
STEP 2: Greedy selection
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

lastEnd = -∞ (no interval picked yet)
count = 0

─────────────────────────────────────────────────────────
Process [1,2]: start=1, end=2
─────────────────────────────────────────────────────────

Check: Is start (1) >= lastEnd (-∞)?
  YES! This interval doesn't overlap with any previous!

Reasoning:
  - This is the first interval we're considering
  - It ends at time 2
  - By picking this, we leave room for intervals starting at 2 or later

Decision: PICK IT! ✓
  lastEnd = 2
  count = 1

Visual:
  [1, 2]
  |---|
       ^ End at 2, room for intervals >= 2

─────────────────────────────────────────────────────────
Process [2,3]: start=2, end=3
─────────────────────────────────────────────────────────

Check: Is start (2) >= lastEnd (2)?
  YES! 2 >= 2, so this doesn't overlap!

Reasoning:
  - Previous interval ended at 2
  - This one starts at 2
  - They touch but don't overlap ✓
  - This ends at 3, leaving room for intervals >= 3

Decision: PICK IT! ✓
  lastEnd = 3
  count = 2

Visual:
  [1, 2] [2, 3]
  |---|  |---|
              ^ End at 3, room for intervals >= 3

─────────────────────────────────────────────────────────
Process [1,3]: start=1, end=3
─────────────────────────────────────────────────────────

Check: Is start (1) >= lastEnd (3)?
  NO! 1 < 3, so this OVERLAPS!

Reasoning:
  - Previous interval ended at 3
  - This one starts at 1 (before 3)
  - If we picked this, it would overlap with intervals we already picked
  - Specifically, it overlaps with [1,2] and [2,3]!

Visual of overlap:
  [1, 2] [2, 3]
  |---|  |---|
  [1,     3]
  |-------|
   ^^^^^^^ Overlap!

Decision: SKIP IT! ✗
  lastEnd = 3 (unchanged)
  count = 2 (unchanged)

─────────────────────────────────────────────────────────
Process [3,4]: start=3, end=4
─────────────────────────────────────────────────────────

Check: Is start (3) >= lastEnd (3)?
  YES! 3 >= 3, so this doesn't overlap!

Reasoning:
  - Previous interval ended at 3
  - This one starts at 3
  - They touch but don't overlap ✓
  - We can safely add this!

Decision: PICK IT! ✓
  lastEnd = 4
  count = 3

Visual:
  [1, 2] [2, 3] [3, 4]
  |---|  |---|  |---|

  No overlaps! All touching at boundaries ✓

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
STEP 3: Calculate answer
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Total intervals: 4
Intervals kept: 3
Intervals to remove: 4 - 3 = 1 ✓

Intervals kept: [1,2], [2,3], [3,4]
Intervals removed: [1,3]

This is MINIMUM because we kept the MAXIMUM possible!

Step 4: Why Greedy is Optimal - The Proof

Claim: Greedy (picking earliest ending) gives optimal solution

Proof by Exchange Argument:
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Suppose there's an optimal solution O that's different from greedy solution G.

Let's compare the first difference:
  - G picks interval A (earliest ending available)
  - O picks interval B (different interval)

Since we sorted by end time:
  - A ends at time t_a
  - B ends at time t_b
  - We know t_a <= t_b (A ends earlier or same)

Now, we can REPLACE B with A in O's solution:
  - A ends at t_a <= t_b
  - Any interval compatible with B is also compatible with A
    (because A ends earlier, it leaves more room)
  - So replacing B with A doesn't break any compatibility
  - We get a solution at least as good as O!

By repeatedly applying this exchange:
  - We can transform O into G
  - Without making it worse

Therefore: G is optimal! ✓

This proves greedy is correct! 🎯

📝 Implementation - Clean and Simple

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        if (intervals.length == 0) return 0;

        // Sort by end time (ascending)
        Arrays.sort(intervals, (a, b) -> a[1] - b[1]);

        int count = 1;  // First interval always selected
        int lastEnd = intervals[0][1];

        // Greedily pick non-overlapping intervals
        for (int i = 1; i < intervals.length; i++) {
            // If current interval doesn't overlap with last picked
            if (intervals[i][0] >= lastEnd) {
                count++;  // Pick this interval
                lastEnd = intervals[i][1];  // Update last end
            }
            // Else: skip this interval (it overlaps)
        }

        // Minimum removals = Total - Maximum kept
        return intervals.length - count;
    }
}

🔍 Complete Dry Run

Input: [[1,2], [2,3], [3,4], [1,3]]

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
SORTING
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Sort by end time:
  [[1,2], [2,3], [1,3], [3,4]]

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
INITIALIZATION
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

count = 1 (first interval [1,2] always picked)
lastEnd = 2 (first interval ends at 2)

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
ITERATION
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

i=1: [2,3]
  start=2 >= lastEnd=2? YES
  Pick! count=2, lastEnd=3

i=2: [1,3]
  start=1 >= lastEnd=3? NO (1 < 3)
  Skip! count=2, lastEnd=3

i=3: [3,4]
  start=3 >= lastEnd=3? YES
  Pick! count=3, lastEnd=4

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

Intervals kept: count = 3
Total intervals: 4
Intervals to remove: 4 - 3 = 1 ✓

📊 Complexity Analysis

Time Complexity: O(n log n)

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

OPTIMAL! 🎯

Space Complexity: O(1)

Only using a few variables
Sorting is in-place (or O(log n) for recursion stack)

---

💡 Alternative Greedy Implementation

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        if (intervals.length == 0) return 0;

        // Sort by end time
        Arrays.sort(intervals, (a, b) -> a[1] - b[1]);

        int removals = 0;
        int lastEnd = intervals[0][1];

        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] < lastEnd) {
                // Overlap! Need to remove this interval
                removals++;
            } else {
                // No overlap, update lastEnd
                lastEnd = intervals[i][1];
            }
        }

        return removals;
    }
}

This version: - Counts removals directly instead of keeping count - Same logic, different perspective - Same complexity: O(n log n) time, O(1) space

---

🎯 Key Insights Summary

The Three Critical Points:

1. Sort by End Time

Why END, not START?

Ending early leaves more room for future intervals!

Example:
  [1, 10] vs [2, 3]

  Pick [1,10]: Blocks time 1-10
  Pick [2,3]: Only blocks 2-3, leaves 3-10 free!

  Ending early = More opportunities! ✓

2. Greedy Choice is Optimal

Always pick the interval that ends earliest!

Proof:
  - If optimal picks B instead of earlier-ending A
  - We can replace B with A
  - A ends earlier → at least as good
  - Therefore greedy is optimal! ✓

3. Think in Reverse

"Minimum removals" = Total - "Maximum kept"

Easier to think:
  "What's the maximum I can keep?"
  Rather than:
  "What should I remove?"

This leads to the greedy approach! 🎯

---

⚠️ Common Mistakes

// Mistake 1: Sorting by start time
Arrays.sort(intervals, (a, b) -> a[0] - b[0]); // ❌ START!
// ✓ CORRECT: Sort by END
Arrays.sort(intervals, (a, b) -> a[1] - b[1]);

// Mistake 2: Wrong overlap condition
if (intervals[i][0] > lastEnd) { // ❌ Should be >=
// ✓ CORRECT: >= allows touching
if (intervals[i][0] >= lastEnd) {

// Mistake 3: Not handling edge case
// ❌ Forgot empty check
Arrays.sort(intervals, ...);
// ✓ CORRECT:
if (intervals.length == 0) return 0;

// Mistake 4: Counting wrong
int removals = 0;
for (...) {
    if (overlap) count++; // ❌ Counting overlaps wrong
}
// ✓ CORRECT: Total - Kept
return intervals.length - count;

---

📝 Quick Revision Notes

🎯 Core Concept

Problem: Remove minimum intervals to make rest non-overlapping

Key Insight: Minimum removals = Total - Maximum non-overlapping we can keep

Greedy Strategy: 1. Sort by END time 2. Pick intervals that end earliest 3. Skip overlapping ones

Why It Works: Ending early leaves more room for future intervals!

⚡ Quick Implementation

import java.util.Arrays;

public class Solution {
  public int eraseOverlapIntervals(int[][] a) {
    return greedy(a);
  }

  private int greedy(int[][] a) {
    // Approach: no logic, only observation
    // step 1: sort by 2nd index (ascending) alone
    // initial: { 1, 2 }, { 2, 3 }, { 3, 4 }, { 1, 3 }
    // sorted: { 1, 2 }, { 2, 3 }, { 1, 3 }, { 3, 4 }
    // Why sort by 2nd index and not 1st index?
    // Example 1: [1,10], [2,3], [3,4]
    // This makes only 1 correct interval which is [1,10]
    // sort by 2nd index: [2,3], [3,4], [1,10]
    // This makes 2 correct intervals
    // Example 2: [9,10], [2,3], [3,4]
    // sort by 2nd index: [2,3], [3,4], [9,10]
    // All are in correct intervals
    // So, have 2nd index sorted by ascending and we
    // see 1st index does not matter
    Arrays.sort(a, (p1, p2) -> p1[1] - p2[1]);

    int n = a.length;
    int correct = 1;
    int[] prevCorrect = a[0];
    for (int i = 1; i < n; i++) {
      // step 2: increment only if current interval start
      // exceeds or does not overlap with prev (*CORRECT) interval end
      // If no overlap, update prevCorrect
      if (a[i][0] >= prevCorrect[1]) {
        correct++;
        prevCorrect = a[i];
      }
    }

    return n - correct;
  }

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

    System.out.println(
        s.eraseOverlapIntervals(new int[][] { { 1, 2 }, { 2, 3 }, { 3, 4 }, { 1, 3 } }) == 1);
    System.out.println(
        s.eraseOverlapIntervals(new int[][] { { 1, 2 }, { 1, 2 }, { 1, 2 } }) == 2);
    System.out.println(
        s.eraseOverlapIntervals(new int[][] { { 1, 2 }, { 2, 3 } }) == 0);
  }
}

🔑 Key Points

✓ Sort by END time (not start!)
✓ Pick earliest ending intervals
✓ Touching is OK (>= not >)
✓ Count kept, return total - kept
✓ Time: O(n log n), Space: O(1)
✓ Greedy is optimal (proven)

🎪 Memory Aid

"End time sort, the greedy fort!"
"Early end, more friends!"
"Keep the max, remove the rest!"
"Touching OK, overlapping nay!" ✨

---

🎉 Congratulations!

You've mastered Non-overlapping Intervals!

What You Learned:

✅ Interval problems - Overlapping concept
✅ Greedy + Sorting - Powerful combination
✅ End time strategy - Why it's optimal
✅ Activity selection - Classic greedy pattern
✅ Proof of correctness - Exchange argument

The Beautiful Insight:

Complex Interval Problem → Simple Greedy Solution

The key insight:
  Intervals that END EARLY leave more room!

  Think about meetings:
    - Short meetings → fit more in
    - Long meetings → block time

  Same principle:
    - Pick earliest ending
    - Maximize how many you can keep
    - Minimize removals!

This is the power of Greedy:
  One clever observation about ordering
  Leads to optimal solution! 🎯

This is Activity Selection - a classic! ✨

Interview Mastery:

When asked about Non-overlapping Intervals:

1. Understand: "Remove minimum to make non-overlapping"

2. Reframe: "Maximum non-overlapping we can keep?"

3. Key insight: "Sort by END time!
   Intervals ending early leave more room"

4. Greedy: "Pick earliest ending non-overlapping intervals"

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

6. Prove: "Exchange argument shows greedy is optimal"

Shows complete understanding! 💯

You've mastered the classic Activity Selection problem! 🚀✨🎯