925. Tracked Ranges

Hard7.5 points estimatedDesignIntervalsOrdered SetSorting4 hints
RPby Rohit Parihar

A railway keeps a calendar of track sections under inspection. Positions are integers and a section [left, right) covers every position p with left <= p < right, so [10,20) and [20,30) touch without overlapping. Build the class TrackedRanges (no constructor arguments), initially tracking nothing.

  • addRange(left, right) starts tracking every position of [left, right), including those already tracked.
  • queryRange(left, right) returns true only if every position of [left, right) is tracked.
  • removeRange(left, right) stops tracking every position of [left, right).

It always holds that left < right. Keep tracked positions as a few merged intervals, so each call costs O(log n) search plus a shift.

Example 1

Input:
operations = ["TrackedRanges","addRange","queryRange","queryRange","addRange","queryRange","removeRange","queryRange","queryRange","queryRange"]arguments = [[],[20,40],[25,35],[15,25],[40,60],[30,55],[30,35],[30,55],[35,55],[20,30]]
Output:
[null,null,true,false,null,true,null,false,true,true]
Explanation:

[20,40) and [40,60) touch and together cover [20,60). After cutting out [30,35), the query [30,55) fails but [35,55) and [20,30) still hold.

Example 2

Input:
operations = ["TrackedRanges","queryRange","addRange","queryRange","queryRange","removeRange","queryRange","removeRange"]arguments = [[],[1,2],[100,101],[100,101],[100,102],[100,101],[100,101],[1,1000]]
Output:
[null,false,null,true,false,null,false,null]
Explanation:

A single unit range [100,101) can be tracked and untracked; removing from a larger window with nothing tracked inside it changes nothing.

Constraints

1 ≤ left < right ≤ 109

At most 3000 calls in total

How this problem is judged

Answers
Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Input
Each case is an operation log. operations names the class first and then each method call; arguments holds the arguments for each, in the same order. Your answer is one list with a result per operation - null for the constructor and for methods that return nothing.

Expected complexity

Time
O(log n) search + O(n) shift per call
Space
O(n)

What the author was aiming for. Your own solution is not measured against it.

Asked in an interview

Were you asked this in an interview? Say where, anonymously.

Code
Loading the editor…

operations names the class, then each method to call; arguments holds one list of arguments per operation, in the same order.