Greedy Interval Scheduling

Problem Solved

Greedy Interval Scheduling solves the Interval Scheduling problem.

Design and Strategy

The Interval Scheduling problem asks for the maximum number of mutually non-overlapping intervals (jobs, events, tasks) that can be scheduled. A greedy strategy works surprisingly well here: always select the interval that finishes earliest. This choice maximizes the remaining time for subsequent intervals.

Here is the algorithm in more formal steps:

1. Sort all intervals by their finishing time.
2. Initialize an empty list for selected intervals and a variable currentTime = -\infty.
3. For each interval [start, end] in sorted order:
   • If start \geq currentTime:
     • Select the interval.
     • Update currentTime = end.

This algorithm is greedy because it always chooses the locally optimal step—selecting the interval that ends the soonest—without reconsidering earlier decisions.

Implementation in Java, C++, Python

int intervalSchedule(int[][] intervals) {
    Arrays.sort(intervals, (a, b) -> Integer.compare(a[1], b[1]));
    int count = 0, current = Integer.MIN_VALUE;
    for (int[] interval : intervals) {
        if (interval[0] >= current) {
            count++;
            current = interval[1];
        }
    }
    return count;
}

int intervalSchedule(vector> &intervals) {
    sort(intervals.begin(), intervals.end(), [](auto &a, auto &b) {
        return a.second < b.second;
    });
    int count = 0, current = INT_MIN;
    for (auto &interval : intervals) {
        if (interval.first >= current) {
            count++;
            current = interval.second;
        }
    }
    return count;
}

def interval_schedule(intervals):
    intervals.sort(key=lambda x: x[1])
    count = 0
    current = float('-inf')
    for start, end in intervals:
        if start >= current:
            count += 1
            current = end
    return count

Time/Space Analysis

Time Complexity: The sort step takes \(O(n \log n)\), and the single pass over the sorted intervals takes \(O(n)\). So the total time is \(O(n \log n)\).

Space Complexity: The algorithm uses \(O(1)\) extra space if sorting is done in place; otherwise, \(O(n)\) if the sort creates a new list.

Variations/Improvements

• Weighted Interval Scheduling: Maximizes total value rather than number of intervals—requires dynamic programming.
• Minimizing Resource Usage: Instead of maximizing count, minimize the number of machines needed (interval partitioning).
• Allowing Overlaps: Some variants allow limited overlaps (e.g., with buffers or priorities), which changes the strategy.

Links to Resources

• Wikipedia: Interval Scheduling
• GeeksforGeeks: Activity Selection Problem
• VisuAlgo: Greedy Algorithms

Reading Comprehension Questions

1. Why does sorting by end time lead to an optimal solution?
2. What is the time complexity of the algorithm?
3. What condition determines whether an interval is selected?
4. Why is this considered a greedy algorithm?
5. What would happen if we sorted by start time instead?

In-Class Activities

1. Manually apply the algorithm to a set of 6–10 intervals and select the ones chosen.
2. Compare schedules produced by sorting by start vs. end time.
3. Write code to implement the greedy interval scheduler.
4. Test the algorithm on sets with overlapping and non-overlapping intervals.
5. Design an instance where the greedy algorithm fails if sorted by start time instead of end time.
6. Draw interval schedules on a timeline to visualize overlaps.
7. Compare this to the weighted interval scheduling problem and discuss why a different approach is needed.

Homework Problems

1. Step-by-step selection: Given 8 intervals, show which ones are selected by the greedy algorithm and in what order.
2. Bad sorting strategy: Construct an example where sorting by start time leads to a suboptimal selection.
3. Proof of correctness: Prove why selecting the earliest-finishing interval leads to an optimal schedule.
4. Weighted variant: Suggest a case where the greedy algorithm fails to maximize total value in the weighted version.
5. Count comparisons: How many intervals are compared in a run of the algorithm on 10 inputs?
6. Custom intervals: Create a list of 6–10 intervals such that only 3 are selected by the greedy strategy.