Loading page…
Practice problem · easy
A study-room booking page keeps a list of bookings for one room. Each booking is a pair [start, end] in minutes. The room is busy from the start minute up to, but not including, the end minute.
Two bookings clash when they share at least one minute. One booking may end at the minute the next one begins, and that is allowed. The bookings arrive in no particular order.
Write any_clash(bookings).
bookings[i] = [start, end], with start < end.true when at least two bookings clash, and false otherwise.Input: bookings = [[600, 660], [900, 960], [630, 690]]
Output: trueSort by start time, then compare each booking with the one before it. A booking clashes with the previous one when it starts before the previous one ends.
| Pair after sorting | Previous end | Next start | Clash? |
|---|---|---|---|
| [600, 660] then [630, 690] | 660 | 630 | yes, 630 < 660 |
The scan stops at the first clash, so the output is true.
Input: bookings = [[540, 600], [600, 660]]
Output: falseThe first booking ends at minute 600 and the second begins there. They share no minute, so there is no clash.
Input: bookings = [[700, 800], [100, 200], [200, 700]]
Output: falseSorted by start, the bookings form a chain: 100 to 200, 200 to 700, then 700 to 800. Each one starts exactly when the last one ends.
0 ≤ bookings.length ≤ 100,0000 ≤ start < end ≤ 1,000,000 (minutes)Checking every pair of bookings means about n × n / 2 checks, which is 5 × 10^9 at n = 100,000. That is too slow. Sorting costs about n log n, roughly 1.7 million steps, and one scan after it costs n more.
any_clash · runs in your browserCoding is easiest on a laptop. On a phone, read, trace and try small edits.