Most people on the floor at once
The register logs every staff entry (start) and exit (end). Find how many were present at the busiest moment.
- A person counts from start until end; at the exact end they are clocked out.
- The moments considered are the integers inside each shift.
peakStaff(slots: list<Slot>) → int
Go needs a compiler and Drill does not host one yet, so this page is the reference rather than an exercise: the problem, worked examples, and the solution in full. To type it out, the same problem runs in Python.
Where you start
func peakStaff(slots []Slot) int {
}Worked examples
| Call | Result |
|---|---|
peakStaff([]Slot{Slot{Start: 0, End: 100}, Slot{Start: 50, End: 200}, Slot{Start: 60, End: 80}}) | 3 |
peakStaff([]Slot{Slot{Start: 0, End: 100}, Slot{Start: 100, End: 200}}) | 1 |
peakStaff([]Slot{}) | 0 |
peakStaff([]Slot{Slot{Start: 0, End: 10}, Slot{Start: 5, End: 15}, Slot{Start: 10, End: 20}}) | 2 |
Hint
Build a timeline of arrivals and departures, then sweep. Or sort all events.
Reference solution in Go
func peakStaff(slots []Slot) int {
type ev struct {
t, d int
}
events := []ev{}
for _, s := range slots {
events = append(events, ev{s.Start, 1}, ev{s.End, -1})
}
sort.Slice(events, func(i, j int) bool {
if events[i].t == events[j].t {
return events[i].d < events[j].d
}
return events[i].t < events[j].t
})
cur, best := 0, 0
for _, e := range events {
cur += e.d
if cur > best {
best = cur
}
}
return best
}