leetcode 区间

本次题解包括

• 56. Merge Intervals
• 57. Insert Interval

56. Merge Intervals

Given a collection of intervals, merge all overlapping intervals.

For example, Given [1,3],[2,6],[8,10],[15,18], return [1,6],[8,10],[15,18].

题目地址：leetcode Merge Intervals

题目大意: 给定一些区间，进行合并

思路：按照区间的左端点进行排序，从左到右扫描，判断能否合并即可。水~

C++

class Solution {
public:
    vector<Interval> merge(vector<Interval>& intervals) {
        sort(intervals.begin(), intervals.end(), [](const Interval& a, const Interval& b) {
            return a.start < b.start;
        });
        
        vector<Interval> ans;
        for(Interval &cur : intervals){
            if(ans.empty()  ans.back().end < cur.start)
                ans.push_back(cur);
            else{
                ans.back().end = max(ans.back().end, cur.end);
            }
        }
        return ans;
    }

Python

class Solution(object):
    def merge(self, intervals):
        """
        :type intervals: List[Interval]
        :rtype: List[Interval]
        """
        intervals.sort(key=lambda a: a.start)
        ans = []
        for t in intervals:
            if not ans or ans[-1].end < t.start:
                ans.append(t)
            else:
                ans[-1].end = max(ans[-1].end, t.end)
        return ans

 

---

57. 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: Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].

Example 2: Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].

This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].

题目地址：leetcode Insert Interval

题目大意: 给定已经合并好的区间（并且按照左端点从小到大），插入一个区间进去，必要时进行合并

思路：

和上面一题差不多，只不过不用排序。可以用二分搜索找到要插入的区间位置，插入然后合并即可。

当然不一定要二分，顺序搜索也行，复杂度都是O(n)。

C++

class Solution {
public:
	vector<Interval> insert(vector<Interval>& intervals, Interval newInterval) {
		auto iter = upper_bound(intervals.begin(), intervals.end(), newInterval, [](const Interval& a, const Interval& b) {
			return a.start <= b.start;
		});

		// (--iter)->start < newInterval.start
		vector<Interval> ans(intervals.begin(), iter);

		// insert newInterval
		if (!ans.empty() && newInterval.start <= ans.back().end)
			ans.back().end = max(ans.back().end, newInterval.end);
		else
			ans.push_back(newInterval);

		// solve other elements.(maybe overlap)
		for (; iter != intervals.end(); ++iter) {
			if (iter->start <= ans.back().end)
				ans.back().end = max(ans.back().end, iter->end);
			else
				ans.push_back(*iter);
		}

		return ans;
	}
};

 

Python

class Solution(object):
    def insert(self, intervals, newInterval):
        """
        :type intervals: List[Interval]
        :type newInterval: Interval
        :rtype: List[Interval]
        """

        def _binary_search(a, x):
            l, r = 0, len(a)
            while l < r:
                mid = (l + r) >> 1
                if a[mid].start <= x.start:
                    l = mid + 1
                else:
                    r = mid
            return l

        index = _binary_search(intervals, newInterval)
        # intervals[i - 1].start < newInterval.start
        ans = intervals[:index]
        if ans and newInterval.start <= ans[-1].end:
            ans[-1].end = max(newInterval.end, ans[-1].end)
        else:
            ans.append(newInterval)

        for i in range(index, len(intervals)):
            if intervals[i].start <= ans[-1].end:
                ans[-1].end = max(intervals[i].end, ans[-1].end)
            else:
                ans.append(intervals[i])
        return ans

 

本文是leetcode如下的题解

• 56. Merge Intervals
• 57. Insert Interval

更多题解可以查看： https://www.hrwhisper.me/leetcode-algorithm-solution/