All problems

Kiln Wait Queries

Medium · intervals

A pottery studio has a single kiln. Each entry bookings[i] = [start, end] means the kiln is in use from minute start up to, but not including, minute end. So at minute end that booking is over, but the kiln is still busy if another booking covers that minute.

Bookings may overlap or follow each other directly. The kiln is in use at a minute whenever at least one booking covers it.

Customers walk in at the minutes listed in queries, and each wants to start firing as soon as the kiln is free. For each queries[i], find the earliest minute that is at or after queries[i] when the kiln is not in use.

Return a list with one answer per query, in the same order as queries. If the kiln is already free at the minute a customer arrives, the answer is that same minute.

Examples

Example 1

Input: bookings = [[1, 4], [4, 6], [10, 12]], queries = [0, 1, 4, 6, 10, 11]

Output: [0, 6, 6, 6, 12, 12]

The first two bookings run back to back from minute 1 to minute 6, so a customer arriving at minute 1 or 4 waits until 6. Minute 0 and minute 6 are already free.

Example 2

Input: bookings = [[2, 8], [3, 5], [5, 9]], queries = [5, 9]

Output: [9, 9]

The bookings overlap and keep the kiln busy until minute 9, so a customer at minute 5 waits until 9. At minute 9 the kiln is free.

Example 3

Input: bookings = [[5, 6]], queries = [4, 5, 6]

Output: [4, 6, 6]

Only minute 5 is busy.

Constraints