A storage engine tracks which row ids are live as a list of half-open ranges. Range [a, b] means ids a, a + 1, ..., b - 1 (so [4, 7] is the three ids 4, 5, 6). The ranges never overlap, but they are not necessarily sorted: the engine keeps them in the order they were written.
Read the ranges one after another, in list order, and write down each id they cover. That gives a flat sequence; position is a 0-based index into it. Write
remove_point(ranges: list[list[int]], position: int) -> list[list[int]]
that deletes the id at position and returns the new list of ranges:
- The range holding that id is replaced in place by what is left of it: two ranges if the id was strictly inside, one shorter range if it was at either end, and nothing if the range held only that id.
- All other ranges stay exactly as they were, in the same order.
- If
position < 0orposition >=the total number of covered ids, raiseIndexError. - Don't modify the input list.
ranges = [[20, 23], [3, 5], [9, 10]]
# flat sequence: 20, 21, 22, 3, 4, 9
remove_point(ranges, 1) # [[20, 21], [22, 23], [3, 5], [9, 10]] 21 was in the middle
remove_point(ranges, 3) # [[20, 23], [4, 5], [9, 10]] 3 was the start of [3, 5]
remove_point(ranges, 5) # [[20, 23], [3, 5]] [9, 10] held only 9
remove_point(ranges, 6) # raises IndexError
Constraints: up to 10**5 ranges, each with a < b, and ids up to 10**12, so a single range can cover a trillion ids. Writing out the flat sequence is not an option; aim for O(number of ranges).