Interval Set Subtraction

Given two sorted, non-overlapping lists of half-open integer intervals a and b, compute the set difference a \ b, the portions of a not covered by b.

Each interval [start, end) includes start but excludes end. Return the result as a sorted, non-overlapping list of intervals.

Examples

Example 1

Input:
a = [[1, 10]]
b = [[3, 5]]

Output: [[1, 3], [5, 10]]
Explanation: The range [1, 10) minus [3, 5) leaves [1, 3) and [5, 10).

Example 2

Input:
a = [[1, 3], [5, 8], [10, 15]]
b = [[2, 6], [9, 11]]

Output: [[1, 2], [6, 8], [11, 15]]