Total price range covered by quotes

Question

Several quotes each cover a price range [low, high], and the ranges may overlap. Compute the total length of the price axis that is covered by at least one quote, overlaps counted once.

ranges = [[1, 3], [2, 5], [7, 9]]
-> 6            # covered [1,5] (length 4) and [7,9] (length 2)

Return the total covered length. Aim for $O(n \log n)$ .

Accepted Answer

Sort the ranges by low end. Sweep left to right, maintaining the current merged block [curstart, curend]. If the next range starts within the current block, extend curend; otherwise the block is finished, add its length to the total and start a new block. Add the final block's length after the loop. Tracing [[1, 3], [2, 5], [7, 9]]: the first two merge into [1, 5] (length 4); [7, 9] is disjoint (length 2). The total is 6. Time O(n \log n) for the sort, space O(1) beyond it. Remember to add the last block after the loop, it is never "closed" by a following disjoint range. Take max for curend s…

Total price range covered by quotes

Your answer

More Coding questions