TRT
Sign in

Advanced · Module 16 · Lesson 3 of 4

Scheduling and intervals

To fit the most non-overlapping intervals, always take the one that ends first. A 'greedy stays ahead' proof shows why, and the same rule solves a family of removal, arrow and partition problems.

Pro — members onlyAbout 14 minutes

By the end you can

  • Select the largest set of non-overlapping intervals by earliest end time
  • Prove it with a greedy-stays-ahead argument, and refute the rules that fail
  • Apply the rule to related problems, and recognize when weights require DP instead

Builds on Exchange arguments, Intervals and sweeping.

01 · A question first

A conference room receives dozens of booking requests for one day. Accepting as many meetings as possible seems to require trying combinations. One rule, always accept the meeting that ends earliest among those that still fit, is provably optimal. Why does the end time matter, rather than the start time or the length?

Make a guess before you read on.

02 · The idea

Members only

Unlock the full lesson

This lesson is part of the membership. Join to read it in full, along with every other premium deep dive.

What's inside

  • The interval scheduling problem
  • Three rules that fail, one that works
  • Greedy stays ahead
  • The same rule in disguise
  • Scheduling in practice
  • When greedy isn't enough
  • Pseudocode & Multi-Language Implementations (C++, Java, Python)
  • Complexity Derivation, Edge Cases & Common Mistakes
See plansAlready a member? Sign in

03 · Practice

Practice · medium · LeetCodeNon-overlapping intervalsFind the fewest intervals to remove so the rest don't overlap, by keeping as many as possible with the earliest-end rule.Practice · medium · LeetCodePartition labelsSplit a string into as many pieces as possible so each letter appears in only one piece, using each letter's last position.Practice · medium · LeetCodeMinimum number of arrows to burst balloonsShoot the fewest arrows to burst every horizontal balloon, shooting at the earliest end each time.

Asked in interviews

Something wrong with this lesson? Report a problem