All problems

Busy Hour Queries

Medium · binary search

The Harbour Museum writes down every visit as [arrive, leave]: the minute a visitor walked in and the minute they walked out. Both minutes count, so a visitor is inside the museum at every minute from arrive up to and including leave.

The manager has a list of minutes she is curious about. For each queries[i], work out how many visitors were inside at that minute.

Return a list with one count per query, in the same order as queries. A query may be answered with 0 if the museum was empty then.

Examples

Example 1

Input: visits = [[1, 4], [2, 6], [5, 8]], queries = [0, 2, 4, 5, 9]

Output: [0, 2, 2, 2, 0]

At minute 4 the first visitor is still there, on their last minute, so the count is 2. At minute 5 the first has gone and the third has arrived.

Example 2

Input: visits = [[3, 3]], queries = [2, 3, 4]

Output: [0, 1, 0]

A visitor who arrives and leaves in the same minute is inside for exactly that minute.

Constraints