AI Hints
Home›DSA in Python Tutorial›Greedy Algorithms
DSA in Python · Lesson 89 of 132

Practice: Meeting Rooms

Greedy that works.

⏱ 2 min read▶ Video at 1:46:28🎓 Free
Watch this lesson in the DSA in Python courseWatch on YouTube ↗Full DSA in Python course

You have one meeting room, and lots of meeting requests, each with a start and an end time. Fit in as many meetings as possible. Pause. Which meeting should you pick first?

Practice: Meeting Rooms
From the video: Practice: Meeting Rooms
  • One room
  • Lots of requests
  • Fit in as many as possible

Earliest finish first

The greedy trick is to always pick the meeting that finishes earliest. That leaves the most time for everything else. We sort by end time, then take each meeting that starts after the last chosen one ends. Run it. Three meetings fit, and it can be proven that no plan fits more.

meetings.pypython
def most_meetings(meetings):
    chosen, last_end = [], 0
    for start, end in sorted(meetings, key=lambda m: m[1]):
        if start >= last_end:
            chosen.append((start, end))
            last_end = end
    return chosen

requests = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (5, 9), (6, 10), (8, 11), (8, 12), (2, 14)]
print(most_meetings(requests))
Output
[(1, 4), (5, 7), (8, 11)]

Trusting a greedy choice

A greedy algorithm is correct only if the greedy choice can never hurt you later. Picking the earliest finish never blocks a better plan, so it's safe. For coins with strange values, the biggest coin can block a better plan, so it isn't. When in doubt, try to find a counter example, like we did with the coins.

keyvalue
Earliest finishprovably optimal
Biggest coinfails for odd coins
Test itlook for a counter example
Costusually a sort, O(n log n)

Summary

Picking the meeting that ends earliest fits the most meetings, and it's provably optimal. Next, dynamic programming, for when greedy isn't enough.

Key takeaways
  • Sort by end time
  • Take if it fits
  • Greedy, and correct
Next up: Dynamic Programming — solve each small problem once