Intervals Example: How Many Charging Points a Car Park Needs

Cars charge from arrival to departure: count arrivals as +1 and departures as −1 in time order, and the highest running count is the number of points.

Counting the most intervals that overlap at once takes a sweep: list every start and end as an event, sort the events by time, and keep a running count. The question rarely says overlap. A car park has electric charging points, and five cars book them for the hours from arrival to departure: 8 to 11, 9 to 12, 10 to 14, 11 to 13 and 12 to 15. A car leaving at 11 frees its point for one arriving at 11. How many points does the car park need?

How many charging points?

Three. At no time are more than three cars charging, because each car arriving at 11 or 12 takes the point another car frees at that moment.

Each arrival adds 1 to the number of points in use and each departure subtracts 1; the answer is the highest count reached. These times are half-open, meaning a car's time includes its arrival hour but not its departure hour, so a departure at 11 and an arrival at 11 do not overlap. The sweep encodes that by processing a departure before an arrival at the same time. The table shows each event in order, from the run.

The sweep, with departures first at a tie
Time	Event	Running count
8	Car 1 arrives	1
9	Car 2 arrives	2
10	Car 3 arrives	3
11	Car 1 leaves	2
11	Car 4 arrives	3
12	Car 2 leaves	2
12	Car 5 arrives	3
13	Car 4 leaves	2
14	Car 3 leaves	1
15	Car 5 leaves	0

The listing runs the sweep with the tie rule and with it reversed, and then counts the same thing a second way: a min-heap, a structure that always gives up its smallest value first, holds the departure times of the cars charging. Each arriving car frees the earliest departure if it has passed, then adds its own, and the heap's final size is the answer.

charging.pypy

import heapq


def points_by_sweep(cars: list[tuple[int, int]], departures_first: bool = True) -> int:
    events = [(arrive, 1) for arrive, _ in cars] + [(leave, -1) for _, leave in cars]
    tie_rank = 1 if departures_first else -1
    events.sort(key=lambda event: (event[0], event[1] * tie_rank))
    in_use = most = 0
    for _, change in events:
        in_use += change
        most = max(most, in_use)
    return most


def points_by_heap(cars: list[tuple[int, int]]) -> int:
    departures: list[int] = []
    for arrive, leave in sorted(cars):
        if departures and departures[0] <= arrive:
            heapq.heappop(departures)
        heapq.heappush(departures, leave)
    return len(departures)


cars = [(8, 11), (9, 12), (10, 14), (11, 13), (12, 15)]
print("departures first at a tie:", points_by_sweep(cars), "points")
print("arrivals first at a tie:  ", points_by_sweep(cars, departures_first=False), "points")
print("min-heap of departures:   ", points_by_heap(cars), "points")

OutputRan with python:3.14.8-slim-trixie (Python 3.14.8)

departures first at a tie: 3 points
arrivals first at a tie:   4 points
min-heap of departures:    3 points

Processing arrivals first at a tie gives 4, because it treats the car leaving at 11 and the one arriving at 11 as charging together. Which rule is right depends on the times, not on the code: half-open slots free a point at the boundary, and closed intervals, such as the concept's, overlap when they touch. Both methods are O(n log n) for n cars, the sweep for sorting 2n events and the heap for sorting the cars and its n pushes.

← → move through sections and cards