I've been given the following problem: "You want to build an algorithm that allows you to build blocks along a number line, and also to check if a given range is block-free. Specifically, we must allow two types of operations:

1. [1, x] builds a block at position x.
2. [2, x, size] checks whether it's possible to build a block of size size that begins at position x (inclusive). Returns 1 if possible else 0.

Given a stream of operations of types 1 and 2, return a list of outputs for each type 2 operations."

I tried to create a set of blocks so we can lookup in O(1) time, that way for a given operation of type 2, I loop in range(x, x size) and see if any of those points are in the set. This algorithm runs too slowly and I'm looking for alternative approaches that are faster. I also tried searching the entire set of blocks if the size specified in the type 2 call is greater than len(blocks), but this also times out. Can anyone think of a faster way to do this? I've been stuck on this for a while.

CodePudding user response：

Store the blocks in a red-black tree (or any self-balancing tree), and when you're given a query, find the smallest element in the tree greater than or equal to x and return 1 if it's greater than x size. This is O(n mlogn) where n is the number of blocks, and m is the number of queries.

If you use a simple binary search tree (rather than a self-balancing one), a large test case with blocks at (1, 2, 3, ..., n) will cause your search tree to be very deep and queries will run in linear (rather than logarithmic) time.