Show problems as
Classic problem #2402HardArrayHash TableSortingHeap (Priority Queue)Simulation

Meeting Rooms III

Real-world version: Busiest Dye Vat
Tracked in this browser only
Read Meeting Rooms III on LeetCode(opens in a new tab)

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

A dye house owns vats interchangeable vats, numbered 0 through vats - 1.

batches[i] = [begin, finish] is a booked batch that asks for a vat at time begin and would hand it back at time finish. The batches are not listed in any particular order, but no two of them ask for a vat at the same time.

The floor supervisor deals with the batches in increasing order of their begin time. When a batch's turn comes:

  • if one or more vats are standing idle at that moment, the batch goes into the idle vat with the smallest number;
  • if every vat is occupied, the batch queues and starts the instant a vat is next handed back, still running for its booked length of finish - begin. Should more than one vat be handed back at that same instant, the batch takes the smallest of their numbers.

A vat counts as idle again at the very instant a batch hands it back, so a batch asking for a vat at that instant may use it.

Return the number of the vat that handles the most batches. When several vats handle that same number of batches, return the smallest of their numbers.

Examples

Example 1

Input
vats = 2, batches = [[0, 5], [1, 3], [6, 7]]
Output
0

The batch beginning at 0 goes into vat 0 and hands it back at 5. The batch beginning at 1 finds vat 0 occupied and goes into vat 1, handing it back at 3. At time 6 both vats are idle, so the last batch goes into vat 0. Vat 0 handled two batches and vat 1 handled one.

Example 2

Input
vats = 3, batches = [[0, 100], [1, 100], [2, 3], [4, 5], [6, 7]]
Output
2

Vats 0 and 1 are taken until time 100 by the first two batches. Each of the three short batches finds those two occupied and vat 2 idle, so vat 2 handles three batches while the others handle one each.

Example 3

Input
vats = 2, batches = [[0, 5], [1, 6]]
Output
0

One batch goes into each vat, so both handled one batch and the smaller vat number is reported.

Constraints

  • 1 <= vats <= 100
  • 1 <= batches.length <= 10^5
  • batches[i].length == 2
  • 0 <= begin_i < finish_i <= 5 * 10^5
  • All the values of begin_i are unique.

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 busiest_dye_vat(vats: int, batches: list[list[int]]) -> int:
Java
public int busiestDyeVat(int vats, int[][] batches)

More on the same topics