Greedy choices and intervals interview questions
Sorting intervals by start or end, sweeping through events, and greedy rules you can prove with an exchange argument.
– interview-ready · 12 questions in this topic
– of 12 tried
Saved on this device. Interview-ready means you got it right on two different days. Guesses and hints count for less.
Questions
- Combine overlapping bookings into blocksPredict
- Fewest bookings to cancel so none clashPick the fix
- How many rooms do the bookings need at once?Predict
- Add a booking to a sorted list of separate blocksPredict
- Can you hop to the last tile?Predict
- Fewest hops to the last tilePredict
- Where to start a delivery loop so the van never runs dryPredict
- Cut a string into the most chunks so no letter crosses a cutPredict
Practise this topic
Flashcards · 22
Flip, then say if you knew it. Needs JavaScript; every answer is also on its question page.
Quick quiz · 12 questions
One exercise per question, checked as you go. Needs JavaScript.
Mock interview · 2 sets
Timed, out loud, then tick what you covered. Needs JavaScript.
Quick facts
Recall the answer first, then tap Show to check.
list.sort(key=...)Python's sort is stable and O(n log n);
key=lambda iv: iv[1]sorts intervals by end time.Sorting tuples
Tuples and lists compare item by item, so sorting
[start, end]pairs sorts by start, then end.operator.itemgettersorted(xs, key=itemgetter(1))is a fast, readable way to sort by the second field.Kotlin
sortedByintervals.sortedBy { it[0] }returns a new sorted list;sortBysorts a mutable list in place. Both are stable.Half-open intervals
Treating a booking as [start, end) means one that ends at 3 and one that starts at 3 do not clash.
Printable cheat sheet · Review your weak spots in this topic
Share your progress
Sources: Topic outline informed by the Tech Interview Handbook by Yangshun Tay and the NeetCode 150 pattern grouping by neetcode-gh, both MIT licensed. Every problem, solution and explanation is written by Best Latest Apps. Credits and license