L8. Non-Overlapping Intervals | Greedy Algorithms

This chapter covers the classic Non-Overlapping Intervals problem, exploring how it directly mirrors the "N Meetings in One Room" problem. By applying a greedy strategy focused on interval end times, we can efficiently find the minimum number of interval removals required to eliminate all overlaps.

1. Problem Statement: Understanding Intervals and Overlaps

We are given an array of $n$ intervals, where each interval consists of a starting point and an ending point. Our objective is to find the minimum number of removals required so that no remaining intervals overlap.

• Definition of an Interval: A pair [start, end].
• Definition of Overlapping: Two intervals overlap if they intersect at any point other than their exact endpoints. For example, [1, 2] and [2, 3] share the endpoint 2, but in this specific problem, touching at endpoints is NOT considered an overlap. Thus, [1, 2] and [2, 3] can coexist without conflicting. However, [1, 2] and [1, 3] or [2, 3] and [1, 3] overlap internally and cannot coexist.

Real-Life Analogy: Scheduling Exclusive Events

Analogy: Imagine you manage a single conference room and people keep submitting requests for time slots. Some requests clash with others. Instead of manually guessing which ones to cancel, you want to find the absolute fewest cancellations needed so that all remaining meetings can happen sequentially without colliding.

2. The Core Prerequisite: Connection to "N Meetings in One Room"

Before solving this problem directly, the instructor highlights a vital shortcut: this problem is the exact inverse of the "N Meetings in One Room" problem (from the same playlist).

• In "N Meetings in One Room", the goal is to maximize the number of meetings you can attend.
• In "Non-Overlapping Intervals", the goal is to minimize the removals.

If we can find the maximum number of non-overlapping intervals we are allowed to keep, we simply subtract that count from the total number of intervals ($n$) to get our minimum removals:

3. Naive vs. Greedy Approach

When faced with interval scheduling problems, students often consider suboptimal or overly complex strategies:

4. Step-by-Step Evolution of the Greedy Solution

Let's trace a concrete example to see how the greedy algorithm operates on an array of intervals.

Example Dataset

Consider the following raw intervals:

• [1, 2]
• [3, 4]
• [0, 5]
• [5, 7]
• [7, 9]
• [5, 9]

Step 1: Sort by End Time

We sort all intervals based on their ending times in ascending order:

1. [1, 2] (Ends at 2)
2. [3, 4] (Ends at 4)
3. [0, 5] (Ends at 5)
4. [5, 7] (Ends at 7)
5. [7, 9] (Ends at 9)
6. [5, 9] (Ends at 9)

Step 2: Iterate and Select Greedily

We pick the first interval by default because finishing as early as possible leaves the most time for subsequent intervals.

Calculation

• Total Intervals ($n$): 6
• Maximum Non-Overlapping Intervals (Count): 4 ([1, 2], [3, 4], [5, 7], [7, 9])
• Minimum Removals: $6 - 4 = 2$

5. Complete Code Implementation

Below is the clean implementation discussed in the lecture, utilizing custom sorting by end time and a single-pass greedy check.

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

        // Sort intervals based on their ending times
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[1], b[1]));

        int count = 1; // We can always take at least the first interval
        int lastEndTime = intervals[0][1];

        // Iterate through remaining intervals
        for (int i = 1; i < intervals.length; i++) {
            // If the current interval's start time is greater than or equal to the last end time
            if (intervals[i][0] >= lastEndTime) {
                count++;
                lastEndTime = intervals[i][1]; // Update last end time
            }
        }

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

6. Complexity Analysis

7. Summary and Key Takeaways

• Problem Inverse: Non-Overlapping Intervals is structurally the exact inverse of the "N Meetings in One Room" problem. Maximize the non-overlapping subset first, then subtract from $n$.
• Greedy Choice Property: Always sort intervals by their ending times rather than their starting times. Finishing sooner maximizes remaining availability.
• Endpoint Rule Handling: In this specific problem definition, touching endpoints (e.g., ending at 7 and starting at 7) do not constitute an overlap (start >= lastEndTime).
• Algorithm Efficiency: Achieves an optimal $O(n \log n)$ time complexity via sorting and a single $O(n)$ greedy pass.
• Space Optimization: Requires constant extra space $O(1)$ beyond the sorting stack frame, modifying or evaluating references directly.
• Practice & Pattern Recognition: Recognizing interval problems as greedy sorting exercises becomes intuitive with regular practice across similar scheduling problems.