Explanation:

Place an obstacle at x = 7 for query 0. A block of size at most 7 can be placed before x = 7.
Place an obstacle at x = 2 for query 2. Now, a block of size at most 5 can be placed before x = 7, and a block of size at most 2 before x = 2.

Constraints

1 <= queries.length <= 15 * 10^4
2 <= queries[i].length <= 3
1 <= queries[i][0] <= 2
1 <= x, sz <= min(5 * 104, 3 * queries.length)
The input is generated such that for queries of type 1, no obstacle exists at distance x when the query is asked.
The input is generated such that there is at least one query of type 2.

Solution

Method 1 – Ordered Set (Binary Search Tree)

Intuition

To efficiently insert obstacles and answer range queries, we maintain a sorted set of obstacle positions. For each type 2 query, we check all intervals between obstacles (including 0 and x as boundaries) to see if any interval can fit the block.

Approach

Use a balanced BST or ordered set to store obstacle positions.
For each query:
- If type 1, insert x into the set.
- If type 2, find all obstacles in [0, x] and check the gaps between consecutive obstacles (including

Related Tags