Find the first free slot in a day
A scheduling assistant looks at a day of bookings and offers the earliest time a meeting of a given length would fit.
- All times are minutes since midnight. Bookings arrive sorted and do not overlap each other.
- The meeting must fit entirely between the start and end of the working day.
- A meeting may begin the moment a booking ends.
- A length of zero or less, or a day with no room, gives null.
nextFreeSlot(busy: list<Slot>, dayStart: int, dayEnd: int, minutes: int) → 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 nextFreeSlot(busy []Slot, dayStart int, dayEnd int, minutes int) *int {
}Worked examples
| Call | Result |
|---|---|
nextFreeSlot([]Slot{Slot{Start: 540, End: 600}}, 480, 1020, 30) | pInt(480) |
nextFreeSlot([]Slot{Slot{Start: 480, End: 540}}, 480, 1020, 30) | pInt(540) |
nextFreeSlot([]Slot{Slot{Start: 480, End: 1020}}, 480, 1020, 30) | nil |
nextFreeSlot([]Slot{Slot{Start: 540, End: 600}, Slot{Start: 610, End: 700}}, 480, 1020, 90) | pInt(700) |
Hint
Sweep a cursor from the start of the day: before each booking, check whether the gap is wide enough, then jump the cursor past it.
Reference solution in Go
func nextFreeSlot(busy []Slot, dayStart int, dayEnd int, minutes int) *int {
if minutes <= 0 {
return nil
}
cursor := dayStart
for _, s := range busy {
if s.Start-cursor >= minutes {
return &cursor
}
if s.End > cursor {
cursor = s.End
}
}
if dayEnd-cursor >= minutes {
return &cursor
}
return nil
}