Maximum Concurrent Server Connections

Reported in interviews at Two Sigma

Problem statement

A server handles $n$ clients. Client $i$ is connected from time start[i] to end[i], with both endpoints inclusive. The server's peak traffic is the maximum number of clients connected at the same instant. Return that peak count (an integer).

serverTraffic(start: List[int], end: List[int]) -> int

Constraints

  • $1 \le n$, times are non-negative integers.

Example

start = [1, 6, 2, 0]
end   = [8, 7, 6, 10]
-> 4

At time $6$ all four clients are connected: client 0 on $[1, 8]$, client 1 on $[6, 7]$, client 2 on $[2, 6]$ and client 3 on $[0, 10]$ (client 2 still counts at $6$ because ends are inclusive). So the peak is $4$.

Follow-up (not graded): how would you also report the earliest time at which the peak is reached?

Show hint

Where along the time axis can the number of connected clients actually change?

Relevant roles: ML Engineer, MLOps Engineer, Forward Deployed Engineer and AI Engineer.

Related free problems