# How to Solve Interval Scheduling Problems Using a Greedy Approach > Master interval scheduling problems with a greedy approach. Learn to efficiently select non-overlapping intervals by sorting and picking based on end times. Maximize your interval selections. - Repository: [DonglaiFu/fucking-algorithm](https://github.com/labuladong/fucking-algorithm) - Tags: how-to-guide - Published: 2026-02-25 --- **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. ```java Arrays.sort(intvs, (a, b) -> Integer.compare(a[1], b[1])); ``` ```python 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. ```java 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. ```java 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** ```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** ```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)`. ```java 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. ```java 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.