An airport has podCount private rest pods numbered from 0 to podCount - 1. Travelers reserve these pods for specific time periods while waiting for their flights.

Each reservation is written as "start,end" and represents the half-open time period [start, end). Its duration is end - start. Every reservation has a different start time.

Assign every reservation to a pod using the rules below. Return the number of the pod used for the most reservations.

Assignment Rules

• All pods are available initially.
• Reservations are processed in increasing order of their original start times.
• If one or more pods are available at a reservation's original start time, assign the available pod with the smallest number.
• If every pod is occupied, delay the reservation until the earliest time a pod becomes available.
• If multiple pods become available at that earliest time, assign the pod with the smallest number.
• A delayed reservation keeps its original duration.
• If multiple travelers are waiting, the reservation with the earlier original start time receives the next available pod first.
• A pod becomes available at the exact time its current reservation ends.

Class

AirportRestPodPlanner

Method

findMostUsedPod

int findMostUsedPod(int podCount, List<String> reservations)

Parameters

• podCount: The number of available rest pods.
• reservations: The requested reservation periods. Each string uses the format "start,end".

Returns

Return the number of the pod used for the most reservations. If multiple pods are used the same highest number of times, return the smallest pod number.

Constraints

• 1 ≤ podCount ≤ 100
• 1 ≤ reservations.size() ≤ 100,000
• Each value in reservations contains exactly two integers in the format "start,end".
• 0 ≤ start < end ≤ 500,000
• Every reservation has a unique start value.
• The reservations may be provided in any order.

Examples

Example 1

findMostUsedPod( podCount = 2, reservations = List.of( "2,9", "3,6", "4,8", "7,10", "8,11"))

Output: 1

The first two reservations use pods 0 and 1. The remaining reservations are delayed when necessary. Pod 0 is used twice and pod 1 is used three times, so the result is 1.

Example 2

findMostUsedPod( podCount = 3, reservations = List.of( "3,7", "0,20", "6,8", "2,6", "5,6", "1,4"))

Output: 2

The reservations are processed by their start times even though the input is unordered. Pods 0, 1, and 2 are used one, two, and three times respectively.

Example 3

findMostUsedPod( podCount = 2, reservations = List.of( "1,4", "2,5", "6,9", "7,10"))

Output: 0

Both pods are used twice. Pod 0 is returned because it has the smaller number.