Website Summary Files Commits Branches @commit @diff @stats
path: root / Additional / Additional-2023-SI / IntervalCollection.cpp
blob: 0ac2c76af9d57d2fa31b51bcd85e2f6307ef2e48 (plain) (blame)
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);
}