Greedy Interval Scheduling

Today's Concepts

1. The Greedy Philosophy: Local vs. Global Optimum
2. The Interval Scheduling Problem: Defining the Goal
3. Exploring Heuristics: Why Intuitive Greedy Choices Fail
4. The Winning Strategy: Earliest Finish Time
5. Proving Correctness: The Exchange Argument

Concept 1: The Greedy Philosophy: Local vs. Global Optimum

Before we dive into a specific problem, let's establish the mindset behind greedy algorithms.

Technical Explanation

A greedy algorithm builds up a solution piece by piece, always choosing the next piece that offers the most obvious and immediate benefit. It makes a locally optimal choice in the hope that this sequence of local optima will lead to a globally optimal solution.

The main advantages are speed and simplicity. The main disadvantage is that they often don't work. For this reason, as the UIUC lecture notes emphasize, every greedy algorithm requires a proof of correctness. Without a proof, a greedy approach is just a heuristic—a rule of thumb that might give a good-enough solution, but not necessarily the best one.

Metaphor: The Blindfolded Hill Climber

Imagine you are blindfolded and placed somewhere on a mountain range. Your goal is to reach the highest possible point. A greedy strategy would be to feel the ground around you at every step and always move in the direction that is steepest upwards.

This might lead you to the top of a small hill (a local optimum), but you might miss the much taller peak right next to it (the global optimum). Greedy algorithms work only for special "mountain ranges" where every local peak is also the highest peak. Our job today is to show that the Interval Scheduling problem has such a special structure.

Concept 2: The Interval Scheduling Problem: Defining the Goal

Let's apply this greedy thinking to a foundational problem that appears frequently in scheduling systems, resource allocation, and, of course, technical interviews.

Technical Explanation

The problem is simple to state:

• Input: A set of n requests (jobs, meetings, classes), each with a specific start time $s_i$ and finish time $f_i$.
• Constraint: A single resource (a conference room, a CPU, a person) can only handle one request at a time. Two requests i and j are compatible if they don't overlap (i.e., if $f_i\le s_j$ or $f_j\le s_i$).
• Goal: Find a subset of mutually compatible requests of the maximum possible size.

This problem is also known as the Activity Selection Problem. In LeetCode, it often appears as "Non-overlapping Intervals" (#435), where the goal is framed as finding the minimum number of intervals to remove to make the rest non-overlapping. This is exactly the inverse of our goal: Total Intervals - Max Compatible Intervals = Min Removals.

Concept 3: Exploring Heuristics: Why Intuitive Greedy Choices Fail

The first step in designing a greedy algorithm is to propose a "greedy choice" or heuristic. Let's explore a few intuitive but flawed ideas. Developing the skill to find counter-examples is crucial for interviews.

To see these failures in action, the MIT OpenCourseWare lecture provides excellent visual counter-examples.

Here's a summary of the failed heuristics discussed in the video:

1. Greedy Choice: Earliest Start Time.

   • Heuristic: Pick the interval that starts first.

   • Why it fails: A very long interval might start earliest but block out many other shorter, compatible intervals.

     Caption: Choosing the long interval that starts at t=0 prevents us from choosing the four shorter intervals. The optimal solution of size 4 is missed.

2. Greedy Choice: Shortest Interval.

   • Heuristic: Pick the interval with the smallest duration ($f_i-s_i$).

   • Why it fails: A very short interval can be strategically placed to conflict with two other intervals that would otherwise be compatible.

     Caption: Choosing the shortest interval in the middle prevents us from picking the two longer intervals on either side, leading to a suboptimal solution of size 1 instead of 2.

3. Greedy Choice: Fewest Conflicts.

   • Heuristic: For each interval, count how many other intervals it overlaps with. Pick the one with the minimum number of conflicts.
   • Why it fails: This is a very tempting but complex heuristic that also fails. A carefully constructed example can show that picking the "least conflicting" interval can eliminate a large, dense group of compatible intervals.

Concept 4: The Winning Strategy: Earliest Finish Time

As revealed in the MIT video, the correct greedy choice is surprisingly simple.

Technical Explanation

The Algorithm: Earliest Finish Time (EFT)

1. Sort all intervals in increasing order of their finish times.
2. Initialize an empty solution set, A.
3. Pick the first interval from the sorted list and add it to A. Let's say its finish time is last_finish_time.
4. Iterate through the rest of the sorted intervals. For each interval i, if its start time s_i is greater than or equal to last_finish_time, it means it's compatible.
5. If it's compatible, add interval i to A and update last_finish_time to i's finish time.
6. Return A.

The Intuition:
Why does this work? By always picking the interval that finishes earliest, we free up the resource as soon as possible. This maximizes the remaining time for other requests to be scheduled. It's the most "resource-considerate" choice you can make at any point.

Concept 5: Proving Correctness: The Exchange Argument

Stating the algorithm is easy. Proving it's optimal is what separates a good engineer from an elite one. The most common technique for proving greedy algorithms is the exchange argument.

The core idea is to show that the greedy solution is just as good as any arbitrary optimal solution.

Proof Summary (Exchange Argument)

Let's formalize the argument from the video:

1. Let $G=\{g_1,g_2,\dots ,g_k\}$ be the solution from our greedy algorithm, sorted by finish times.
2. Let $O=\{o_1,o_2,\dots ,o_m\}$ be any optimal solution, also sorted by finish times. We want to prove $k=m$.
3. The "Greedy Stays Ahead" Lemma: The greedy algorithm stays ahead in the sense that for any $i\ge 1$, the finish time of the $i$-th greedy choice is no later than the finish time of the $i$-th choice in the optimal solution. That is, $f(g_i)\le f(o_i)$.
   • Base Case (i=1): The greedy algorithm picks the interval with the absolute earliest finish time, so $f(g_1)\le f(o_1)$ must be true.
   • Inductive Step: Assume $f(g_i)\le f(o_i)$. $g_{i+1}$ is the first interval in the sorted list that starts after $f(g_i)$. $o_{i+1}$ must start after $f(o_i)$. Since $f(g_i)\le f(o_i)$, $o_{i+1}$ is a valid candidate for the greedy algorithm after $g_i$. The greedy algorithm will pick the one with the earliest finish time, so it will pick something at least as good as $o_{i+1}$. Thus, $f(g_{i+1})\le f(o_{i+1})$.
4. The Contradiction: Now, assume for contradiction that the optimal solution has more intervals than the greedy one ($m>k$). This would mean there is an interval $o_{k+1}$ in the optimal solution. By our lemma, we know $f(g_k)\le f(o_k)$. Since $o_{k+1}$ is compatible with $o_k$, its start time must be $\ge f(o_k)$. Therefore, $s(o_{k+1})\ge f(o_k)\ge f(g_k)$. This means $o_{k+1}$ is a compatible interval that the greedy algorithm could have chosen after $g_k$. But the greedy algorithm stopped at $k$ intervals, meaning it found no more compatible intervals. This is a contradiction.
5. Conclusion: Therefore, our assumption that $m>k$ must be false. Since $O$ is optimal, we know $m\ge k$. Together, this means $m=k$. The greedy algorithm produces a solution of optimal size.

Implementation and Complexity

Finally, let's translate this into clean, interview-ready code.

def max_compatible_intervals(intervals):
    """
    Solves the Interval Scheduling problem using a greedy approach.
    
    Time Complexity: O(n log n) due to sorting.
    Space Complexity: O(1) if sorting in-place, or O(n) if a copy is made.
    
    Args:
        intervals: A list of lists, where each inner list is [start, end].
        
    Returns:
        A list of the maximum set of compatible intervals.
    """
    if not intervals:
        return []

    # Step 1: Sort intervals by their finish times
    # The key is a lambda function that tells sort() to use the second element (index 1)
    intervals.sort(key=lambda x: x[1])
    
    # Step 2: Initialize the solution set and track the last finish time
    solution = []
    
    # Add the first interval (the one with the earliest finish time) to the solution
    solution.append(intervals[0])
    last_finish_time = intervals[0][1]
    
    # Step 3: Iterate through the rest of the intervals
    for i in range(1, len(intervals)):
        current_start_time = intervals[i][0]
        
        # Step 4: If the current interval is compatible, add it to the solution
        if current_start_time >= last_finish_time:
            solution.append(intervals[i])
            last_finish_time = intervals[i][1] # Update the last finish time
            
    return solution

# Example
requests = [[1, 4], [3, 5], [0, 6], [5, 7], [3, 8], [5, 9], [6, 10], [8, 11], [8, 12], [2, 13], [12, 14]]
optimal_schedule = max_compatible_intervals(requests)
print(f"Maximum number of compatible intervals: {len(optimal_schedule)}")
print(f"Optimal schedule: {optimal_schedule}")
# Expected output: [[1, 4], [5, 7], [8, 11], [12, 14]]

Conclusion

Today you transitioned from the exhaustive world of DP to the fast-but-risky world of Greedy Algorithms. You learned that while many greedy ideas seem plausible, they often fail. The key is to find the right greedy choice and, most importantly, to be able to prove its optimality.

Key Takeaways:

• Greedy vs. DP: Greedy algorithms make locally optimal choices, while DP solves subproblems to find a globally optimal one. Greedy is faster but requires a correctness proof.
• Interval Scheduling: This classic problem is optimally solved by a greedy algorithm.
• The Right Heuristic: For interval scheduling, the winning strategy is to always pick the compatible activity that finishes earliest. This frees up the resource quickly, maximizing future options.
• The Exchange Argument: This is a fundamental proof technique. You show that any optimal solution can be transformed, step-by-step, into the greedy solution without losing optimality, proving they are equivalent in quality.

Preview of the Next Lesson:
We will continue our exploration of greedy algorithms with another canonical problem: Huffman Coding. You will learn how to use a priority queue to implement a greedy strategy that builds an optimal prefix code for data compression. This will reinforce your understanding of greedy choices and their proofs in a completely different context.