aboutsummaryrefslogtreecommitdiff
path: root/insert_interval.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'insert_interval.cpp')
-rw-r--r--insert_interval.cpp39
1 files changed, 39 insertions, 0 deletions
diff --git a/insert_interval.cpp b/insert_interval.cpp
new file mode 100644
index 0000000..09c6fe7
--- /dev/null
+++ b/insert_interval.cpp
@@ -0,0 +1,39 @@
+#include "leetcode.h"
+
+class Solution {
+public:
+ vvd(int) insert(vvd(int) & intervals, vector<int> &newInterval) {
+ const int START = 0, END = 1;
+ int s = newInterval[START], e = newInterval[END];
+ vvd(int) left, right;
+ for (auto &curr : intervals) {
+ if (curr[END] < s)
+ left.push_back(curr);
+ else if (curr[START] > e)
+ right.push_back(curr);
+ else {
+ s = min(s, curr[START]);
+ e = max(e, curr[END]);
+ }
+ }
+ vvd(int) ans;
+ ans.insert(ans.end(), left.begin(), left.end());
+ ans.push_back({s, e});
+ ans.insert(ans.end(), right.begin(), right.end());
+ return ans;
+ }
+};
+
+int main() {
+ Solution obj;
+ vvd(int) intervals1 = {{1, 3}, {6, 9}},
+ intervals2 = {{1, 2}, {3, 5}, {6, 7}, {8, 10}, {12, 16}};
+ vector<int> newInterval1 = {2, 5}, newInterval2 = {4, 8};
+ for (auto i : obj.insert(intervals1, newInterval1))
+ for (auto j : i)
+ cout << j << ' '; // expect: [[1,5],[6,9]]
+ cout << endl;
+ for (auto i : obj.insert(intervals2, newInterval2))
+ for (auto j : i)
+ cout << j << ' '; // expect: [[1,2],[3,10],[12,16]]
+}