Katkat
Back

Assign bookings to minimum tennis courts

AtlassianMachine Learning Engineer · Onsite
MediumMachine Learning EngineerOnsiteCoding & Algorithms

Last updated

This problem tests your ability to manage overlapping time intervals using a greedy approach, specifically requiring the calculation of the maximum number of concurrent bookings to determine the minimum resource count.

Problem Statement

You are managing a tennis facility and have a list of requested bookings, where each booking is represented as a tuple (start_time, end_time). Your goal is to determine the minimum number of tennis courts required to accommodate all bookings without any overlaps. A court can be reused immediately after a booking ends.

Function Signature

def min_tennis_courts(bookings: List[Tuple[int, int]]) -> int:

Constraints

  • bookings length: 1 to 10^5
  • start_time < end_time
  • Time values are integers ranging from 0 to 10^9

Examples

Example 1: Input: bookings = [(1, 4), (2, 5), (6, 9)] Output: 2 Explanation: At time 2, the first two bookings overlap. We need 2 courts. By time 6, the first two have finished, so we only need 1 court.

Example 2: Input: bookings = [(1, 2), (2, 3), (3, 4)] Output: 1 Explanation: Bookings are sequential (end time of one equals start time of the next), so 1 court is sufficient.

Edge Cases

  • Empty input list.
  • All bookings overlap perfectly.
  • Bookings that touch at the endpoints (e.g., end time 2, start time 2).

Hints

Hint 1

Consider the bookings as two separate streams of events: 'starts' and 'ends'.

Hint 2

If you sort both the start times and end times independently, you can iterate through them to track the number of active bookings.

Hint 3

A booking occupies a court during the interval [start, end), meaning the court becomes free exactly at the end time.

Follow-up questions

  • How would your approach change if you had to return the specific court assignment for each booking?
  • What is the time and space complexity of your solution, and can you optimize it further?
  • If the tennis courts have different hourly rates, how would you modify the algorithm to minimize the total cost rather than just the number of courts?