How to Solve Interval Scheduling Problems Using a Greedy Approach

To solve interval scheduling problems, sort intervals by end time in ascending order, select the first interval, then greedily pick subsequent intervals whose start times are greater than or equal to the end time of the last selected interval.

The interval scheduling problem—also known as finding the Maximum Set of Non‑Overlapping Intervals—is a classic greedy algorithm exercise documented in the labuladong/fucking-algorithm repository. This article explains the greedy strategy implemented in 动态规划系列/贪心算法之区间调度问题.md, provides runnable Java and Python code, and covers common variations such as LeetCode 435 and 452.

Understanding the Interval Scheduling Problem

The problem asks you to select the largest possible subset of closed intervals [start, end] such that no two chosen intervals intersect. Intervals are considered overlapping if they share any point in time. The optimal solution requires maximizing the count of compatible intervals rather than maximizing total duration or other metrics.

The Greedy Strategy for Interval Scheduling

The algorithm works because the problem satisfies the greedy‑choice property: selecting the interval that ends earliest never prevents you from reaching an optimal solution. This allows a simple three‑step procedure that runs in O(n log n) time and O(1) extra space.

Step 1: Sort by End Time

Arrange all intervals in ascending order based on their end value. This pre‑processing step dominates the runtime complexity.

Arrays.sort(intvs, (a, b) -> Integer.compare(a[1], b[1]));

intvs.sort(key=lambda x: x[1])

Step 2: Select and Scan

Initialize your selection with the first interval from the sorted list (the one that finishes earliest). Track the lastEnd variable to remember when the most recently chosen interval finishes.

int count = 1;
int lastEnd = intvs[0][1];

Step 3: Skip Overlapping Intervals

Iterate through the remaining intervals. Whenever an interval’s start is greater than or equal to lastEnd, it is compatible with the current schedule. Add it to the solution and update lastEnd to its end value. Otherwise, discard the interval and continue.

for (int[] interval : intvs) {
    int start = interval[0];
    if (start >= lastEnd) {
        count++;
        lastEnd = interval[1];
    }
}

Implementation in Java and Python

The intervalSchedule method in 动态规划系列/贪心算法之区间调度问题.md provides a reference Java implementation. Below is the complete code with an equivalent Python version.

Java

class Solution {
    public int intervalSchedule(int[][] intvs) {
        if (intvs.length == 0) return 0;
        // Sort by end time
        Arrays.sort(intvs, (a, b) -> Integer.compare(a[1], b[1]));

        int count = 1;                // at least one interval is selected
        int lastEnd = intvs[0][1];    // end of the last chosen interval

        // Linear scan
        for (int[] interval : intvs) {
            int start = interval[0];
            if (start >= lastEnd) {   // non-overlapping
                count++;
                lastEnd = interval[1];
            }
        }
        return count;
    }
}

Python

def interval_schedule(intvs):
    if not intvs:
        return 0
    # Sort by end time

    intvs.sort(key=lambda x: x[1])

    count = 1
    last_end = intvs[0][1]

    # Scan

    for start, end in intvs:
        if start >= last_end:        # non-overlapping

            count += 1
            last_end = end
    return count

Time and Space Complexity Analysis

The greedy algorithm for interval scheduling runs in O(n log n) time, where n is the number of intervals. This complexity is dominated by the sorting step. The subsequent linear scan operates in O(n) time. The algorithm uses O(1) auxiliary space (excluding the input storage and sorting overhead), as it only maintains a counter and the lastEnd variable.

Common Variations of Interval Scheduling

The core greedy logic adapts easily to related problems by modifying the boundary condition or post‑processing the result.

Minimum Number of Intervals to Remove (LeetCode 435)

This variant asks for the minimum deletions required to make the remaining intervals non‑overlapping. Instead of computing the maximum compatible set directly, calculate totalIntervals - intervalSchedule(intervals).

public int eraseOverlapIntervals(int[][] intvs) {
    int n = intvs.length;
    return n - intervalSchedule(intvs);
}

Minimum Number of Arrows to Burst Balloons (LeetCode 452)

Balloons are represented as intervals where touching boundaries count as overlapping (one arrow bursts both). Change the compatibility condition from start >= lastEnd to start > lastEnd to ensure that touching intervals trigger a new arrow.

public int findMinArrowShots(int[][] intvs) {
    if (intvs.length == 0) return 0;
    Arrays.sort(intvs, (a, b) -> Integer.compare(a[1], b[1]));
    int arrows = 1;
    int lastEnd = intvs[0][1];
    for (int[] interval : intvs) {
        if (interval[0] > lastEnd) {   // strict inequality for inclusive overlap
            arrows++;
            lastEnd = interval[1];
        }
    }
    return arrows;
}

Summary

• Interval scheduling problems seek the largest subset of non‑overlapping intervals, solvable via a greedy approach documented in labuladong/fucking-algorithm.
• Sort by end time first, then perform a linear scan to select compatible intervals, yielding O(n log n) time and O(1) space.
• Adapt the boundary condition (>= vs >) to handle variations such as LeetCode 435 (minimum removals) and LeetCode 452 (bursting balloons).
• Exchange arguments prove optimality: replacing any optimal solution’s first interval with the earliest‑finishing interval never reduces the solution size.

Frequently Asked Questions

Why does sorting by end time work better than sorting by start time?

Sorting by end time satisfies the greedy‑choice property, ensuring that the interval finishing earliest leaves the maximum remaining time for future selections. If you sort by start time, you might select a long interval that blocks multiple shorter compatible intervals, leading to a sub‑optimal count. The exchange argument proves that an optimal solution always exists that includes the earliest‑finishing interval.

Can the greedy approach handle intervals with equal end times?

Yes. When multiple intervals share the same end time, the greedy algorithm remains correct regardless of which one you select first, because any interval ending at that time leaves identical remaining capacity for the future. The sorting implementation should use a stable comparator (e.g., comparing end times, then start times if needed) to ensure deterministic behavior, but the final count will be optimal either way.

How do I modify the algorithm for open intervals?

For open intervals (start, end) where the endpoints themselves are not included, the non‑overlap condition changes from start >= lastEnd to start > lastEnd. This is equivalent to the inclusive‑boundary case used in the balloon problem (LeetCode 452). Simply adjust the comparison operator in the linear scan loop; the sorting step and overall complexity remain unchanged.

Is the interval scheduling greedy algorithm always optimal?

Yes, for the standard maximum cardinality objective (maximizing the count of non‑overlapping intervals), the greedy algorithm that selects the earliest‑finishing interval first is provably optimal. However, if the objective changes—for example, maximizing total duration covered or weighted interval scheduling where each interval has a profit—the greedy approach may fail. In those cases, dynamic programming or weighted interval scheduling algorithms are required instead.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}