question 500 Production Readiness Capstone · hard

Trips in the last hour, quickly

The dispatch dashboard shows, for each trip, how many trips started in the 60 minutes before it (including itself). The current version compares every trip with every earlier trip, which is fine for ten trips and hopeless for a night. Pickup times are given as minutes after midnight, already sorted. Make it fast without changing the answers.

Functionrecent_counts(minutes); minutes is a sorted list of pickup times in minutes

Returnsa list: for each trip, the number of trips whose time is greater than its time - 60 and not later than its own (equal times count; those later in the list too)

Constraintfor 600 trips, at most 15,000 comparisons of times (the current version needs about 400,000)

Examples

callrecent_counts([5, 20, 20, 64, 70, 200])returns[1, 3, 3, 4, 4, 1]

callrecent_counts([])returns[]

callrecent_counts([0, 30, 59, 60, 61])returns[1, 2, 3, 3, 4]