The Stablemaster's Busiest Hour
The inn's stablemaster needs to know how many stalls to build before the harvest fair.
Her ledger holds today's boardings. You are given bookings, a list of two-element lists [arrive, depart] of non-negative integers with arrive < depart. The entries are in no particular order, and times may repeat. A horse occupies a stall from arrive up to but not including depart, so a horse arriving at exactly the time another departs may take that freed stall.
Return a two-element list [stalls, hour], where stalls is the greatest number of horses present at any single moment of the day, and hour is the earliest time at which that many horses are present at once.
If bookings is empty, return [0, -1].
Write stallTally(bookings). Times can be as large as 10^9.
examples
- case 1
bookings of [[1, 4], [2, 5], [7, 9]][2, 2] - from time 2 to time 4 two horses are stabled at once, and time 2 is the first such moment - case 2
bookings of [[1, 3], [3, 5], [5, 7]][1, 1] - each horse leaves exactly as the next arrives, so only one stall is ever in use, first occupied at time 1 - case 3
bookings of [[5, 6], [5, 6], [1, 2], [1, 2]][2, 1] - two horses are present at both time 1 and time 5, and the earliest of those moments is 1 - case 4
bookings of [][0, -1]
- reward
- 310 XP
- signature
stallTally
TypeScript, run as ES2022 — types are stripped, not checked. If a JS engine would run it, so will we.
- two overlap in the middle
- touching bookings never overlap
- empty ledger
- single horse
- nested bookings and a later cluster
- tie goes to the earliest hour
- identical bookings stack
- large times, unsorted