Algorithm to Remove a Interval from Segments

Given a sorted list of disjoint intervals, each interval intervals[i] = [a, b] represents the set of real numbers x such that a <= x < b. We remove the intersections between any interval in intervals and the interval toBeRemoved. Return a sorted list of intervals after all such removals.

Example 1:
Input: intervals = [[0,2],[3,4],[5,7]], toBeRemoved = [1,6]
Output: [[0,1],[6,7]]

Example 2:
Input: intervals = [[0,5]], toBeRemoved = [2,3]
Output: [[0,2],[3,5]]

Constraints:
1 <= intervals.length <= 10^4
-10^9 <= intervals[i][0] < intervals[i][1] <= 10^9

Hints:
Solve the problem for every interval alone.
Divide the problem into cases according to the position of the two intervals.

Given the list of the intervals are sorted already, we then can iterate the interval in order, and compare the interval A and the interval-to-remove B which has a few cases:

– A and B could be disjoint – they are not connected at all.
– A could be total inside B aka. A includes B or B includes A.
– A and B could be intersecting each other.

Then, we can deal with these situations separately.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
public:
    vector<vector<int>> removeInterval(vector<vector<int>>& intervals, vector<int>& toBeRemoved) {
        vector<vector<int>> r;
        auto start = toBeRemoved[0];
        auto end = toBeRemoved[1];
        for (const auto &n: intervals) {
            if (n[1] < start || (n[0] > end)) {
                r.push_back(n);
            } else if (n[0] >= start && (n[1] <= end)) {
                continue;
            } else if (n[0] < start && (n[1] > end)) {
                r.push_back({n[0], start});
                r.push_back({end, n[1]});
            } else if (n[0] < start && (n[1] < end)) {
                r.push_back({n[0], start});
            } else if (n[1] > start && (end < n[1])) {
                r.push_back({end, n[1]});
            }
        }
        return r;
    }
};

class Solution {
public:
    vector<vector<int>> removeInterval(vector<vector<int>>& intervals, vector<int>& toBeRemoved) {
        vector<vector<int>> r;
        auto start = toBeRemoved[0];
        auto end = toBeRemoved[1];
        for (const auto &n: intervals) {
            if (n[1] < start || (n[0] > end)) {
                r.push_back(n);
            } else if (n[0] >= start && (n[1] <= end)) {
                continue;
            } else if (n[0] < start && (n[1] > end)) {
                r.push_back({n[0], start});
                r.push_back({end, n[1]});
            } else if (n[0] < start && (n[1] < end)) {
                r.push_back({n[0], start});
            } else if (n[1] > start && (end < n[1])) {
                r.push_back({end, n[1]});
            }
        }
        return r;
    }
};

We could simplify the cases into two: if lower(A) is smaller than lower(B), then an interval after removal will be {lower(A), min(lower(B), upper(A))}. Similarly, if upper(A) is bigger than upper(B), then an interval to insert is {max(upper(B), lower(A)), upper(A)}.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution {
public:
    vector<vector<int>> removeInterval(vector<vector<int>>& intervals, vector<int>& toBeRemoved) {
        vector<vector<int>> r;
        auto start = toBeRemoved[0];
        auto end = toBeRemoved[1];
        for (const auto &n: intervals) {
            if (n[0] < start) {
                r.push_back({n[0], min(start, n[1])});
            }
            if (n[1] > end) {
                r.push_back({max(end, n[0]), n[1]});
            }
        }
        return r;
    }
};

class Solution {
public:
    vector<vector<int>> removeInterval(vector<vector<int>>& intervals, vector<int>& toBeRemoved) {
        vector<vector<int>> r;
        auto start = toBeRemoved[0];
        auto end = toBeRemoved[1];
        for (const auto &n: intervals) {
            if (n[0] < start) {
                r.push_back({n[0], min(start, n[1])});
            }
            if (n[1] > end) {
                r.push_back({max(end, n[0]), n[1]});
            }
        }
        return r;
    }
};

For example, A = [1, 6] and B is [4, 7]. The intervals after removal are: [1,4] // first if check
If A = [1, 6] and B is [4, 5]. The intervals after removal are [1, 4] and [5, 6]. // second if check.

The time complexity is O(N) where N is the number of the intervals. What if there are many intervals (assumed there are M intervals) to remove? Could you do better than O(MN).

Could you solve this problem using similar algorithm? How to Compute the Interval List Intersections using Two Pointer Algorithms?

–EOF (The Ultimate Computing & Technology Blog) —