8000 added 120 · konanrobot/LeetCode@9fa6438 · GitHub
[go: up one dir, main page]
Skip to content

Commit 9fa6438

Browse files
pezypezy
committed
added 120
1 parent 4fbfb7e commit 9fa6438

File tree

3 files changed

+74
-0
lines changed

3 files changed

+74
-0
lines changed

‎120. Insert Interval/README.md

Lines changed: 15 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,15 @@
1+
这道题仍然考察的是特殊的数据结构。
2+
3+
这个 `Interval` 本质上就是一个 `std::pair`.
4+
5+
最初的序列保证有序，那么查找 `newInterval` 将会很快（类似二分查找即可）。找首部的时候，根据 start，找尾部的时候，根据 end.
6+
7+
若 newInterval 的 start 落在了某个 interval 之间，那么修改 start, 并从该 interval 处开始删除。
8+
9+
同理 end 落在了某个 interval 之间，那么修改 end, 并从上面开始处一直删除到该 interval.
10+
11+
修改好 start 和 end, 并删除重复区域后，直接插入即可。
12+
13+
若没有落在任何 interval 之间，那么也是直接插入。
14+
15+
思路很简单，我偷懒直接用了 `std::lower_bound` 算法。

‎120. Insert Interval/TEST.cc

Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,32 @@
1+
#define CATCH_CONFIG_MAIN
2+
#include "../Catch/single_include/catch.hpp"
3+
#include "solution.h"
4+
5+
std::vector<int> showIntervals(const std::vector<Interval> &intervals) {
6+
std::vector<int> ret;
7+
for (const auto &interval : intervals) {
8+
ret.push_back(interval.start);
9+
ret.push_back(interval.end);
10+
}
11+
return ret;
12+
}
13+
14+
TEST_CASE("Insert Interval", "insert")
15+
{
16+
Solution s;
17+
18+
SECTION("Example 1")
19+
{
20+
std::vector<Interval> vec{Interval(1,3), Interval(6,9)};
21+
Interval newInterval(2,5);
22+
std::vector<int> ret{1,5,6,9};
23+
REQUIRE(ret == showIntervals(s.insert(vec, newInterval)));
24+
}
25+
SECTION("Example 2")
26+
{
27+
std::vector<Interval> vec{Interval(1,2),Interval(3,5),Interval(6,7),Interval(8,10),Interval(12,16)};
28+
Interval newInterval(4,9);
29+
std::vector<int> ret{1,2,3,10,12,16};
30+
REQUIRE(ret == showIntervals(s.insert(vec, newInterval)));
31+
}
32+
}

‎120. Insert Interval/solution.h

Lines changed: 27 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,27 @@
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> insert(vector<Interval> &intervals, Interval newInterval) {
15+
auto low = std::lower_bound(intervals.cbegin(), intervals.cend(), newInterval, [](const Interval& lhs, const Interval& rhs){
16+
return lhs.start < rhs.start;
17+
});
18+
if (low != intervals.cbegin() && std::prev(low)->end >= newInterval.start) { --low; newInterval.start = low->start; }
19+
auto up = std::lower_bound(intervals.cbegin(), intervals.cend(), newInterval, [](const Interval& lhs, const Interval& rhs){
20+
return lhs.end < rhs.end;
21+
});
22+
if (up != intervals.cend() && up->start <= newInterval.end) { newInterval.end = up->end; ++up; }
23+
auto insert_pos = intervals.erase(low, up);
24+
intervals.insert(insert_pos, newInterval);
25+
return intervals;
26+
}
27+
};

0 commit comments

Comments
 (0)
0