All problems

Studio Booking Conflicts

Medium · tree dfs

A rehearsal studio takes bookings that all last exactly length minutes. A booking that starts at minute s uses the studio from minute s up to, but not including, minute s + length. So one booking may start at the very minute another one ends.

The start minutes of all existing bookings are stored in a binary search tree with the given root. You are also given a list queries of start minutes that bands would like to book.

For each query t, say whether a new booking starting at t would fit, which means that it shares no minute with any existing booking. Every query is answered on its own: a booking that fits is not added to the tree.

Return a list of booleans, one per query, in the same order as queries. The tree can be empty.

In a binary search tree, for every node all values in its left subtree are smaller and all values in its right subtree are larger. All start minutes are distinct.

Examples

Example 1

Input: root = [100, 40, 160], length = 30, queries = [70, 69, 130, 100]

Output: [true, false, true, false]

A booking at 70 runs until minute 100, just as the booking at 100 starts, so it fits. At 69 it would overlap the booking at 100. At 130 it runs from 130 to 160, which fits. A booking at 100 clashes with the existing one.

Example 2

Input: root = [], length = 5, queries = [0, 12]

Output: [true, true]

With no bookings, everything fits.

Constraints

• The number of nodes is in the range [0, 2000].
• 0 <= Node.val <= 10^6, and all values are distinct.
• The tree is a valid binary search tree.
• 1 <= length <= 10^6
• 1 <= len(queries) <= 2000
• 0 <= queries[i] <= 10^6