Merge interval and Insert interval

题目

Merge interval

Given a collection of intervals, merge all overlapping intervals.

Example 1:

Input: [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]

Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].

Example 2:

Input: [[1,4],[4,5]]
Output: [[1,5]]

Explanation: Intervals [1,4] and [4,5] are considered overlapping.

Insert interval

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).

You may assume that the intervals were initially sorted according to their start times.

Example 1:

Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]

Example 2:

Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]

Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].

解法

Merge interval，首先需要对所有的区间进行排序，排序的准则：

• 先判断区间左侧是否关系：较小者 排序 在前
• 如果左边界相等，根据右边界决定关系，但是这里将右侧大的往前，其实不重要

然后就遍历数组，进行合并即可：

• 前面区间和当前区间没有交集，直接将前面区间放入结果
• 有交集，则进行合并

整体复杂度是： O(NlogN)

Insert interval: 这一题可以偷懒，利用 merge interval 来实现同样的目的。即：

• 将新区间插入，排序
• merge

但是这种做法没有充分利用原来区间就已经有序的条件。插入一个新区间，主要就是判断新区间在原来区间中的 位置。

[], [], [], —, [], [], [], — [], []
[], [], [—], [], [], [] — [], []
[], [], [], —, [], [], [—], [], []
[], [], [—], [], [], [—], [], []

上图中的 dash 线表示新区建的左侧和右侧，它与原区间列表存在上述四种关系。对于上述四种关系，我们对于 dash 线前和 dash 线后的区间可以直接复制到结果中，中间直接和新区间 merge 即可。

那么中关系怎么查找呢？可以利用原来数组就是有序的前提进行二分查找。整体复杂度在 O(N)

思路

• 排序
• 二分查找边界

代码

class Solution {
private:
    typedef vector<int> V;
    typedef vector<V> VV;
    struct Comp {
        bool operator()(vector<int>& lhs, vector<int>& rhs) {
            if (lhs[0] != rhs[0]) return lhs[0] < rhs[0];
            return lhs[1] < rhs[1];
        }
    };
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end(), Comp());
        int size = intervals.size();
        VV result;
        if (size == 0) return result;
        auto prev = intervals[0];
        for (int i = 1; i < size; ++i) {
            auto& a = intervals[i];
            if (prev[1] < a[0]) {
                result.push_back(prev);
                prev = a;
            } else {
                // prev[1] >= a[0]

                prev[1] = max(prev[1], a[1]);
            }
        }
        result.push_back(prev);
        return result;
    }
};

class Solution {
private:
    typedef vector<int> V;
    typedef vector<V> VV;

    struct Comp {
        bool operator()(vector<int>& lhs, vector<int>& rhs) {
            if (lhs[0] != rhs[0]) return lhs[0] < rhs[0];
            return lhs[1] < rhs[1];
        }
    };


public:
    vector<vector<int>> insert1(vector<vector<int>>& intervals, vector<int>& newInterval) {
        intervals.push_back(newInterval);
        sort(intervals.begin(), intervals.end(), Comp());
        int size = intervals.size();
        VV result;
        auto prev = intervals[0];
        for (int i = 1; i < size; ++i) {
            auto& a = intervals[i];
            if (prev[1] < a[0]) {
                result.push_back(prev);
                prev = a;
            } else {
                // prev[1] >= a[0]

                prev[1] = max(prev[1], a[1]);
            }
        }
        result.push_back(prev);
        return result;
    }
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        VV result;
        int size = intervals.size();
        if (size == 0) {
            result.push_back(newInterval);
            return result;
        }

        // corner case

        if (newInterval[1] < intervals[0][0]) {
            result.push_back(newInterval);
            copy(intervals.begin(), intervals.end(), back_inserter(result));
            return result;
        } else if (newInterval[0] > intervals[size-1][1]) {
            copy(intervals.begin(), intervals.end(), back_inserter(result));
            result.push_back(newInterval);
            return result;
        }

        int low = 0;
        int high = size;
        int target = newInterval[0];
        int pos_b = -1;
        while (low < high) {
            int mid = (high - low) / 2 + low;
            auto& h = intervals[mid];
            if (h[0] <= target && h[1] >= target) {
                pos_b = mid; break;
            } else if (h[1] < target) {
                low = mid + 1;
            } else if (h[0] > target) {
                high = mid;
            }
        }
        int low_b = low;
        target = newInterval[1];
        low = 0; high = size;
        int pos_e = -1;
        while (low < high) {
            int mid = (high - low) / 2 + low;
            auto& h = intervals[mid];
            if (h[0] <= target && h[1] >= target) {
                pos_e = mid; break;
            } else if (h[1] < target) {
                low = mid + 1;
            } else if (h[0] > target) {
                high = mid;
            }
        }
        int low_e = low;
        if (pos_e == -1 && pos_b == -1) {
            auto beg = intervals.begin();
            auto end = intervals.begin();
            advance(end, low_b);
            copy(beg, end, back_inserter(result));
            result.push_back(newInterval);
            end = intervals.end();
            advance(beg, low_e);
            copy(beg, end, back_inserter(result));
        } else if (pos_b == -1) {
            auto beg = intervals.begin();
            auto end = intervals.begin();
            advance(end, low_b);
            copy(beg, end, back_inserter(result));
            newInterval[1] = intervals[pos_e][1];
            result.push_back(newInterval);
            advance(beg, min(pos_e + 1, size));
            end = intervals.end();
            copy(beg, end, back_inserter(result));
        } else if (pos_e == -1) {
            auto beg = intervals.begin();
            auto end = intervals.begin();
            advance(end, pos_b);
            copy(beg, end, back_inserter(result));
            newInterval[0] = intervals[pos_b][0];
            result.push_back(newInterval);
            advance(beg, low_e);
            end = intervals.end();
            copy(beg, end, back_inserter(result));

        } else {
            auto beg = intervals.begin();
            auto end = intervals.begin();
            advance(end, pos_b);
            copy(beg, end, back_inserter(result));
            newInterval[0] = intervals[pos_b][0];
            newInterval[1] = intervals[pos_e][1];
            result.push_back(newInterval);
            advance(beg, min(pos_e + 1, size));
            end = intervals.end();
            copy(beg, end, back_inserter(result));
        }
        return result;
    }
};

本文完

.

• ← Previous Post