Show problems as
Classic problem #253MediumArrayTwo PointersGreedySortingHeap (Priority Queue)Prefix Sum

Meeting Rooms II

Real-world version: Peak Charging Bay Demand
Tracked in this browser only
Read Meeting Rooms II on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

Learn the pattern firstSorting · Arrays, animated step by step

A depot is sizing a bank of identical charging bays before opening day. You are given sessions, where sessions[i] = [arrive_i, leave_i] is the minute a vehicle plugs in and the minute it unplugs.

A bay serves one vehicle at a time. A vehicle holds its bay over the half-open span from arrive_i up to leave_i, so a vehicle unplugging at minute t hands the bay straight to a vehicle arriving at minute t. Two sessions that merely touch at an endpoint therefore never contend for a bay.

Return the smallest bay count that lets the depot honour every session in sessions.

Examples

Example 1

Input
sessions = [[4, 9], [9, 14], [14, 20]]
Output
1

Each vehicle unplugs exactly as the next one arrives, so one bay is handed down the whole chain.

Example 2

Input
sessions = [[0, 12], [3, 6], [4, 8]]
Output
3

At minute 4 all three vehicles are plugged in at once, so the depot cannot get by with fewer than 3 bays.

Example 3

Input
sessions = [[10, 20], [30, 40], [15, 35]]
Output
2

The long session spanning minutes 15 to 35 doubles up first with the 10-to-20 session and later with the 30-to-40 one, but the first and second sessions never coincide, so 2 bays suffice.

Constraints

  • 1 <= sessions.length <= 10^4
  • sessions[i].length == 2
  • 0 <= arrive_i < leave_i <= 10^6

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def peak_bay_demand(sessions: list[list[int]]) -> int:
Java
public int peakBayDemand(int[][] sessions)

More on the same topics