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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
|
#include <iostream>
#include <vector>
#include <algorithm>
class IntervalCollection
{
using Iterator = std::vector<std::pair<int, int>>::iterator;
using ConstIterator = std::vector<std::pair<int, int>>::const_iterator;
Iterator getRightmostInterval(int x)
{
std::pair<int, int> searcher = { x, x };
return std::lower_bound(
intervals.begin(),
intervals.end(),
searcher,
[](const std::pair<int, int>& first, const std::pair<int, int>& second) -> bool
{
return first.second < second.second;
}
);
}
ConstIterator getRightmostIntervalConst(int x) const
{
std::pair<int, int> searcher = { x, x };
return std::lower_bound(
intervals.begin(),
intervals.end(),
searcher,
[](const std::pair<int, int>& first, const std::pair<int, int>& second) -> bool
{
return first.second < second.second;
}
);
}
public:
void insert(int x)
{
Iterator right = getRightmostInterval(x);
bool begin = (right == intervals.begin());
Iterator left = begin ? intervals.end() : right - 1;
bool needLeftMerge = !begin && (x - 1 == left->second);
bool needRightMerge = (right != intervals.end()) && (x + 1 == right->first);
if (right != intervals.end() && x >= right->first && x <= right->second)
{
return;
}
if (needLeftMerge && needRightMerge)
{
left->second = right->second;
intervals.erase(right);
}
else if (needLeftMerge)
{
left->second = x;
}
else if (needRightMerge)
{
right->first = x;
}
else
{
intervals.insert(right, { x, x });
}
}
bool contains(int x) const
{
ConstIterator right = getRightmostIntervalConst(x);
return (right != intervals.end() && x >= right->first && x <= right->second);
}
void print() const
{
for (const auto& x : intervals)
{
std::cout << x.first << " " << x.second << std::endl;
}
}
private:
std::vector<std::pair<int, int>> intervals;
};
int main()
{
IntervalCollection ic;
ic.insert(1);
ic.insert(3);
ic.insert(2);
ic.insert(5);
ic.insert(7);
ic.insert(4);
ic.insert(6);
std::cout << ic.contains(1) << " " << ic.contains(10);
}
|