Laundromat Machine Count
You are opening a laundromat that works by reservation. Customers book a washing machine for a time window, in minutes after opening: [10, 40] means they load at minute 10 and the machine is free again at minute 40. A machine that frees up at minute 40 can take a new load that starts at minute 40.
Machines are expensive. Looking at a busy Saturday's reservations, how few machines could have served every customer on time?
Your task
Write machinesNeeded(loads). Each load is [start, end] with start < end. Return the minimum number of machines so that every load can run on some machine, and no machine runs two loads at once.
A load ending at time t and another starting at time t can share a machine. An empty list needs 0 machines.
machinesNeeded(loads: int[][]) → int
Examples
loads = [[0, 45], [10, 40], [40, 70], [50, 95]]
2
From minute 10 to 40 two loads run at once, so you need at least 2 machines. And 2 is enough: machine A runs [0, 45] then [50, 95]; machine B runs [10, 40] then [40, 70].
loads = [[30, 60], [60, 90], [90, 120]]
1
Each load starts exactly when the previous one ends, so one machine handles all three back to back.
Constraints
- 0 ≤ loads.length ≤ 10,000
- 0 ≤ start < end ≤ 1,000,000,000
Start with brute force
For every load's start time, count how many loads are running at that moment (start ≤ t < end) by scanning the whole list. The peak count is the answer, because the busiest moment is always some load's start.
That is n checks of n loads each: O(n²), about 100 million comparisons for 10,000 loads. The scan recounts the same loads again and again; sorting lets you keep a running count instead.
Hints
0 of 4 shown- Hint 1
In the first example, pick any minute and count how many loads are running then. What is the largest count you can find, and how does it relate to the answer?
- Hint 2
You can never use fewer machines than the most loads running at the same moment. It turns out you never need more, either. So the real question is: what is the peak number of loads in progress?
- Hint 3
The count only changes when a load starts (+1) or ends (-1). If you look at those moments in time order, you can track the count as you go. What should happen when an end and a start share the same minute?
- Hint 4
Sort all start times, and separately all end times. Walk through the starts in order; before counting a start, release every load whose end ≤ that start (one pointer into the sorted ends). Track the running count and its maximum. An end at the same minute is released first, because touching loads can share a machine.
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
The answer is the largest number of loads running at the same moment. Fewer machines cannot work at that moment, and that many always suffice, because you can hand each new load any machine that is free. To find the peak, sweep through time: a start adds one running load, an end removes one.
Trace the first example. Starts: [0, 10, 40, 50]. Ends: [40, 45, 70, 95].
- Start 0. No ends ≤ 0. Running 1, peak 1.
- Start 10. No ends ≤ 10. Running 2, peak 2.
- Start 40. The end at 40 is ≤ 40, so release it first: running 1. Then start: running 2. Peak stays 2.
- Start 50. The end at 45 is ≤ 50: release, running 1. Start: running 2. Answer: 2.
Releasing ends with ≤ before counting the start is what lets touching loads share a machine. With < you would report 3 for loads that only hand over a machine. The inner loop never runs past the end of ends: when a start is being counted, that load's own end is still waiting, so there is always an end greater than the current start.
function machinesNeeded(loads) {
const starts = loads.map(l => l[0]).sort((a, b) => a - b);
const ends = loads.map(l => l[1]).sort((a, b) => a - b);
let running = 0, peak = 0, e = 0;
for (const start of starts) {
// Free every machine whose load is done by now.
while (ends[e] <= start) {
running--;
e++;
}
running++;
peak = Math.max(peak, running);
}
return peak;
}def machines_needed(loads):
starts = sorted(s for s, _ in loads)
ends = sorted(e for _, e in loads)
running = peak = e = 0
for start in starts:
# Free every machine whose load is done by now.
while ends[e] <= start:
running -= 1
e += 1
running += 1
peak = max(peak, running)
return peakRun your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.