8000 added 117. Merge Intervals · Ctipsy/LeetCode@62a8e7f · GitHub
[go: up one dir, main page]
Skip to content 8000

Commit 62a8e7f

Browse files
pezypezy
committed
added 117. Merge Intervals
1 parent 86a1021 commit 62a8e7f

File tree

3 files changed

+75
-0
lines changed

3 files changed

+75
-0
lines changed

‎117. Merge Intervals/README.md

Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,30 @@
1+
这道题应该如何着手？
2+
3+
首先我想到的是排序，因为如果所给数据如题目给出的例子一般有序，那非常容易：
4+
5+
[1,3], [2,6], [8,10], [15,18]
6+
^ ^
7+
[1,6], [8,10], [15,18]
8+
9+
只需迭代一遍，比较一下前一个 interval 的 end, 和下一个 interval 的 start 即可。
10+
11+
按照这个朴素的思路，我们飞快的写下如下代码：
12+
13+
```cpp
14+
vector<Interval> ret;
15+
std::sort(intervals.begin(), intervals.end(), [](const Interval &a, const Interval &b){
16+
return a.start < b.start;
17+
});
18+
for (const auto &interval : intervals) {
19+
if (!ret.empty() && interval.start <= ret.back().end)
20+
ret.back().end = std::max(interval.end, ret.back().end);
21+
else ret.push_back(interval);
22+
}
23+
return ret;
24+
```
25+
26+
颤颤巍巍的提交了一下。。。
27+
28+
竟然发现 AC 了，而且效率颇高！！！
29+
30+
难道不是搞笑吗？这是 Hard 难度的题？我走错门了吧？

‎117. Merge Intervals/main.cpp

Lines changed: 19 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,19 @@
1+
#include "solution.h"
2+
#include <iostream>
3+
4+
using namespace std;
5+
6+
int main() {
7+
Solution s;
8+
vector<Interval> vec = {
9+
Interval(15,18),
10+
Interval(8,10),
11+
Interval(2,6),
12+
Interval(1,3)
13+
};
14+
15+
for (const auto &interval : s.merge(vec)) {
16+
std::cout << "[" << interval.start << "," << interval.end << "]" << ",";
17+
}
18+
std::cout << "\b " << std::endl;
19+
}

‎117. Merge Intervals/solution.h

Lines changed: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,26 @@
1+
#include <vector>
2+
using std::vector;
3+
#include <algorithm>
4+
5+
struct Interval {
6+
int start;
7+
int end;
8+
Interval() : start(0), end(0) {}
9+
Interval(int s, int e) : start(s), end(e) {}
10+
};
11+
12+
class Solution {
13+
public:
14+
vector<Interval> merge(vector<Interval> &intervals) {
15+
vector<Interval> ret;
16+
std::sort(intervals.begin(), intervals.end(), [](const Interval &a, const Interval &b){
17+
return a.start < b.start;
18+
});
19+
for (const auto &interval : intervals) {
20+
if (!ret.empty() && interval.start <= ret.back().end)
21+
ret.back().end = std::max(interval.end, ret.back().end);
22+
else ret.push_back(interval);
23+
}
24+
return ret;
25+
}
26+
};

0 commit comments

Comments
 (0)
0