0%

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++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
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/

请我喝杯咖啡吧~