Algorithm to Remove a Interval from Segments

  • 时间:2020-09-15 16:10:27
  • 分类:网络文摘
  • 阅读:104 次

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) —

推荐阅读:
WodrPress实现远程图片本地化插件-Auto_Save_Image  碧沙岗公园作文  世界的奇迹作文700字  初有所成,静待花开  端午包粽子作文350字  成长的温暖作文900字  沙家浜作文400字  中秋节作文1400字:思念在那个秋天  夜晚的华尔兹  擀面皮作文400字 
评论列表
添加评论