Katkat
Back

Assign tennis bookings to minimum courts

AtlassianSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

Design an algorithm to assign a schedule of tennis court bookings to the minimum number of courts required, resolving resource contention efficiently.

Problem Statement

A tennis club accepts booking reservations throughout the day. Each booking is defined by a start time and an end time [start, end]. A court can only host one booking at any given time. If a booking ends at time T, another booking can start on the same court at time T without conflict.

Your task is to assign each booking to a court such that:

  1. No two overlapping bookings share the same court.
  2. The total number of unique courts used is minimized.
  3. Court IDs are labeled starting from 0 to k - 1, where k is the minimum number of courts required.

Return a list of integers assignments of the same length as bookings, where assignments[i] is the court ID assigned to bookings[i]. If there are multiple valid assignments using the minimum number of courts, return any valid assignment.

Function Signature

def assign_courts(bookings: list[list[int]]) -> list[int]:
    pass

Input & Output Format

  • Input: A list of 2-element lists bookings, where bookings[i] = [start, end] represents the start and end time of the i-th booking.
  • Output: A list of integers of length len(bookings), where the element at index i is the 0-indexed court assigned to bookings[i].

Constraints

  • 1 <= len(bookings) <= 10^5
  • 0 <= start < end <= 10^9

Examples

Example 1

Input: bookings = [[1, 5], [2, 6], [5, 8], [6, 9]]
Output: [0, 1, 0, 1]

Explanation:

  • Booking 0 [1, 5] is assigned Court 0.
  • Booking 1 [2, 6] overlaps with Booking 0, so it is assigned Court 1.
  • Booking 2 [5, 8] starts at 5, when Court 0 is now free. It takes Court 0.
  • Booking 3 [6, 9] starts at 6, when Court 1 is now free. It takes Court 1. A total of 2 courts are used, which is minimal.

Example 2

Input: bookings = [[1, 4], [2, 5], [3, 6]]
Output: [0, 1, 2]

Explanation: All three bookings overlap at time 3. A minimum of 3 distinct courts is required.

Edge Cases to Consider

  • Bookings that touch at boundaries (e.g., [1, 3] and [3, 5] do not conflict).
  • All bookings happening concurrently.
  • Bookings provided out of chronological order.

Hints

Hint 1

Sort the bookings by their start times, but be sure to retain the original index of each booking to construct the final output array.

Hint 2

Use a min-heap to keep track of active courts and when they will become available (ordered by end time).

Hint 3

To reuse the lowest available court ID when multiple courts are free, maintain a separate min-heap of free court IDs.

Follow-up questions

  • What changes if each booking requires a fixed 15-minute maintenance/cleaning period between matches on the same court?
  • How would you adapt your solution if some bookings have court type preferences (e.g., clay vs. hard court)?
  • If bookings arrive as a live stream rather than as an offline batch, how would you design the online assignment system, and what trade-offs emerge?