Shared Telescope Night
A university observatory has one big telescope, and astronomers send in requests for time on it. Each request is a window of minutes measured from midnight: [-90, -30] means 10:30 pm to 11:30 pm, and [30, 90] means 12:30 am to 1:30 am.
Only one astronomer can use the telescope at a time, though one session may start the very minute another ends. Too many requests came in for tonight. The scheduler wants to turn down as few of them as possible.
Your task
Write fewestToDecline(requests). Each request is [start, end] with start < end. Return the smallest number of requests to remove so that no two remaining requests overlap.
Two requests overlap if one starts before the other ends. Requests that only touch, like [0, 60] and [60, 120], do not overlap. An empty list returns 0.
fewestToDecline(requests: int[][]) → int
Examples
requests = [[0, 180], [30, 60], [60, 120], [150, 240]]
1
Turn down [0, 180]. The other three then fit one after another: 30 to 60, 60 to 120, and 150 to 240. Declining fewer is impossible, because [0, 180] overlaps all three others, and you cannot keep it alongside them.
requests = [[-60, 30], [-90, -30], [30, 90]]
1
[-90, -30] and [-60, 30] overlap between -60 and -30, so one of them must go. Decline either one: [30, 90] fits after both, since a session may start the minute another ends. So only 1 request is turned down.
Constraints
- 0 ≤ requests.length ≤ 10,000
- -1,000,000,000 ≤ start < end ≤ 1,000,000,000
Start with brute force
Try every subset of requests, check whether it has no overlaps, and keep the largest valid one. The answer is the total minus that size.
There are 2n subsets. With 40 requests that is already about a trillion, and the limit here is 10,000. You need a rule that picks the right requests without trying combinations.
Hints
0 of 4 shown- Hint 1
Turn the question around: declining the fewest requests is the same as keeping the most. Which request would you want to keep first?
- Hint 2
Try some rules on the first example. Keeping the one that starts earliest picks [0, 180] and blocks everything. Keeping the shortest can also fail. What about the request that ends earliest?
- Hint 3
The request that ends earliest leaves the telescope free soonest. Any best schedule can swap its first session for this one without losing anything.
- Hint 4
Sort by end time. Keep a variable
freeAt. For each request in that order: if its start ≥freeAt, keep it and setfreeAtto its end. Otherwise it overlaps something you kept, so count it as declined.
Walkthrough and solution
Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.
How to solve it
Keep as many requests as possible, and always keep the one that ends earliest among those that still fit. Finishing early never hurts: whatever a best schedule keeps first, swapping it for the earliest-ending request leaves the telescope free at least as soon.
Trace the first example. Sorted by end: [30, 60], [60, 120], [0, 180], [150, 240].
[30, 60]: the telescope is free. Keep it. Free again at 60.[60, 120]: 60 ≥ 60, touching is allowed. Keep it. Free at 120.[0, 180]: starts at 0, before 120. It overlaps. Decline.[150, 240]: 150 ≥ 120. Keep it. Free at 240.
Kept 3 of 4, so 1 is declined. Sorting by start instead would grab [0, 180] first and decline the other three.
function fewestToDecline(requests) {
const byEnd = [...requests].sort((a, b) => a[1] - b[1]);
let kept = 0;
let freeAt = -Infinity; // when the telescope is next free
for (const [start, end] of byEnd) {
if (start >= freeAt) { // fits after the last kept session
kept++;
freeAt = end;
}
}
return requests.length - kept;
}def fewest_to_decline(requests):
kept = 0
free_at = float('-inf') # when the telescope is next free
for start, end in sorted(requests, key=lambda r: r[1]):
if start >= free_at: # fits after the last kept session
kept += 1
free_at = end
return len(requests) - keptRun your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.