Cut a Gap Out of Segments

Medium

A set of points on a line is given as a list segments of half-open ranges [a, b): a point x belongs to a range when a ≤ x < b. The ranges are sorted in increasing order and do not overlap. Cut the half-open range gap = [x, y) out of this set, removing every point that falls into it. A range the gap only partly hits gets shorter; a range that strictly contains the gap splits into two pieces. Return what is left in the same form: a sorted list of non-overlapping half-open ranges. Empty pieces are not included.

Example 1

segments=[[-2, 1], [3, 8], [10, 12]], gap=[0, 5] → [[-2, 0], [5, 8], [10, 12]]

[-2, 1) shrinks to [-2, 0), [3, 8) shrinks to [5, 8), and [10, 12) is untouched by the gap.

Example 2

segments=[[0, 9]], gap=[4, 6] → [[0, 4], [6, 9]]

The gap falls in the middle of the segment and splits it into two pieces.

Example 3

segments=[[1, 2], [3, 4]], gap=[0, 10] → []

Constraints

1 ≤ len(segments) ≤ 10⁴
-10⁹ ≤ a < b ≤ 10⁹ for every range
The ranges are sorted and do not overlap: each one ends at or before the start of the next
gap = [x, y], -10⁹ ≤ x < y ≤ 10⁹

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array

Similar problems

Two Boards Holding Water Medium Zero-Sum Triples Medium Triple Sum Nearest the Target Medium Four Numbers to a Target Medium Next Arrangement in Order Medium

Input

segments=[[-2, 1], [3, 8], [10, 12]], gap=[0, 5]

Expected

[[-2, 0], [5, 8], [10, 12]]

Run checks the first 3 tests in your browser. Submit checks all 136 tests on the server, hidden ones included.