CodeWithYash

Intermediate · Module 16 · Lesson 3

Interval scheduling

Select compatible events using ordered endpoints.

15–25 min readLesson 91 of 123

Lesson 91 of 123

1d streak

Theory lesson · Step-by-step

Understand Interval scheduling

Select compatible events using ordered endpoints.

Worked approach

Trace the reasoning step by step

  1. 1State the candidate ordering and local choice made by Interval scheduling.
  2. 2Identify the feasibility condition maintained by the partial solution.
  3. 3Use an exchange or stays-ahead argument to justify the choice.
  4. 4Commit the choice and remove candidates it makes impossible.
  5. 5Search for a counterexample before trusting the greedy rule.

Concrete example

Choose from [1,3], [2,5], [4,6], [6,7].

  1. 1Pick [1,3].
  2. 2Skip [2,5].
  3. 3Pick [4,6], then [6,7].

Three compatible intervals are selected.

What must remain true (Loop Invariant)

After every choice in Interval scheduling, the partial solution can still be extended to an optimum under the proved exchange or stays-ahead argument.

Cost Model

Complexity & Trade-offs

Sort and select
O(n log n)
O(1) auxiliary
The bound follows from the number of states visited and the work performed per transition.

When to use it

  • Scheduling, reachability, coding, matching resources, and minimum-cost growth.
  • Problems with an exchange proof or matroid-like safe choices.
  • Online decisions that maintain a best frontier.

Common mistakes

  • Choosing a plausible local optimum without a proof.
  • Using the wrong sorting key.
  • Applying greedy reasoning when choices interact through future state.

Practice prompts

  • Reproduce the worked Interval scheduling example without looking at the trace.
  • Change one input condition and explain whether the Interval scheduling invariant still holds.
  • Implement the approach, derive its cost, and compare it with a straightforward baseline.

Mastery check

Can you derive it instead of memorizing it?

State the invariant before looking at code.
Explain why every transition is safe.
Construct a worst-case input.
Name one alternative and its trade-off.