Cancel the Fewest
MediumIntervals
Problem
A lecture hall has been double-booked. Each booking in meetings is [start, end], occupying the half-open range [start, end); a booking ending at t and one starting at t do not conflict.
Return the minimum number of bookings that must be cancelled so that the remaining ones never overlap.
Example 1
- Input:
- meetings = [[1, 2], [2, 3], [3, 4], [1, 3]]
- Output:
- 1
Cancel [1, 3); the other three run back to back.
Example 2
- Input:
- meetings = [[1, 2], [1, 2], [1, 2]]
- Output:
- 2
Only one copy can stay.
Example 3
- Input:
- meetings = [[1, 2], [2, 3]]
- Output:
- 0
Constraints
- 1 ≤ meetings.length ≤ 10^5
- -5·10^4 ≤ start < end ≤ 5·10^4
Hint
Show the first hint
Cancelling the fewest is the same as keeping the most. Which booking would you keep first?
Walkthrough
How to approach it
01Clarify before coding
- Are touching bookings a conflict? No, ranges are half-open.
- Do we return the bookings to cancel or just the count? Just the count.
- Can bookings be identical? Yes; all but one copy must go.
02Brute force
Try every subset of bookings, keep the largest one with no overlaps, and return n minus its size.
Cost: O(2^n · n) time: hopeless beyond about 20 bookings.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.