Master the Clock: Solving Interval Problems with Greedy Algorithms

Imagine you are a Hollywood movie director. Five different actors want to pitch you their scripts today, but their availability overlaps. You want to hear as many pitches as possible before the day ends. How do you schedule your day to maximize your meetings? 🎬

This is the classic Interval Scheduling Problem. It is one of the most famous applications of a greedy algorithm, where making a short-sighted, immediate choice actually guarantees the perfect global result.

📅 The Core Problem: Overlapping Time Slots

In computer science, an interval is just a block of time with a definite start time and an end time.

The goal of the Interval Scheduling Problem is simple: given a list of intervals, find the maximum number of mutually compatible intervals. In plain English: pack your schedule with as many non-overlapping events as humanly possible.

Here is a quick look at a sample schedule:

• Meeting A: 1:00 PM – 3:00 PM
• Meeting B: 2:00 PM – 5:00 PM
• Meeting C: 3:00 PM – 4:00 PM

You can't do both A and B, nor B and C, because B overlaps them. Your job is to pick the best combination.

##💡 The Greedy Strategy: What's the Secret Rule?

To solve a problem greedily, you need a rule to sort and pick your options. Let's test a few intuitive rules to see which one works:

1. Pick the earliest start time? No. A meeting starting at 6:00 AM that lasts all day would block every other meeting.
2. Pick the shortest duration? No. A short meeting right in the middle of the day could block two slightly longer meetings on either side of it.
3. Pick the earliest end time? Yes! 🏆

By picking the meeting that finishes first, you free up your schedule as early as possible for the next event. This leaves the maximum amount of remaining daylight to fit in more intervals.

⚙️ The Step-by-Step AlgorithmT

The recipe to solve this problem is incredibly clean and runs in $O(nlogn))$ time (mainly due to sorting):

1. Sort all intervals based on their end times from earliest to latest.
2. Pick the first interval from the sorted list (this is your first confirmed event).
3. Track the end time of this last added interval.
4. Loop through the remaining intervals:
   1. If an interval's start time is greater than or equal to your tracked end time, it is compatible!
   2. Add it to your schedule and update your tracked end time to this new interval's end time.
   3. If it overlaps, skip it.

💻 The Code Blueprint (Python)

def max_intervals(intervals):
    if not intervals:
        return 0
        
    # Step 1: Sort by end times (index 1 of each interval)
    intervals.sort(key=lambda x: x[1])
    
    count = 1
    last_end_time = intervals[0][1] # Step 2 & 3: Pick the first one
    
    # Step 4: Loop through the rest
    for i in range(1, len(intervals)):
        start, end = intervals[i]
        
        # If the next meeting starts after or when the last one ends
        if start >= last_end_time:
            count += 1
            last_end_time = end # Update tracked end time
            
    return count

# Example Usage:
# Meetings: A(1, 3), B(2, 5), C(3, 4)
meetings = [[1, 3], [2, 5], [3, 4]]
print(f"Max meetings you can attend: {max_intervals(meetings)}") 
# Output: 2 (Meeting A then Meeting C)