Covered Stretches of a Number Line
Implement a class RangeTracker that keeps track of which parts of a number line are covered. The range [left, right) holds every number x with left <= x < right, and its length is right - left. Write these methods:
RangeTracker()starts with nothing covered.add(left, right)covers all of[left, right). Returns the length that was not covered before and is covered now.remove(left, right)uncovers all of[left, right). Returns the length that was covered before and is not covered now.is_covered(left, right)returnstrueif all of[left, right)is covered.list_pieces()returns the covered parts as[left, right]pairs in increasing order, with parts that touch joined together: covering[1, 3)and[3, 5)gives the single piece[1, 5].first_gap(x)returns the smallest numbery >= xthat is not covered.
The tests call the methods in sequence and compare every return value. The expected list holds null for the constructor.
Example 1
RangeTracker()
add(10, 20) returns 10
add(30, 40) returns 10
add(15, 35) returns 10
list_pieces() returns [[10,40]]
remove(18, 22) returns 4
list_pieces() returns [[10,18],[22,40]]
is_covered(12, 19) returns false
first_gap(15) returns 18
add(18, 22) returns 4
list_pieces() returns [[10,40]]
Adding [15, 35) covers 10 new units and joins the two pieces into [10, 40]. Removing [18, 22) splits it again, so 18 is the first number at or after 15 that is not covered. Adding [18, 22) back joins everything into one piece.
Constraints
0 <= left < right <= 10**90 <= x <= 10**9- Each test makes
1to40method calls after the constructor.
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.