leetcode

commit 83f406f32d8a429653b488d1db007154d9f2649d
parent 0c8e2ec74a058cda17f411e95566b38b5a837b9a
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Mon,  9 Jan 2023 23:07:19 +0100

Random Problem because Daily was done

Diffstat:
A
Problems/0057.cpp
 | 
25
+++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 26 insertions(+), 0 deletions(-)
diff --git a/Problems/0057.cpp b/Problems/0057.cpp
@@ -0,0 +1,25 @@
+class Solution {
+  typedef vector<int> Interval;
+
+public:
+  vector<Interval> insert(vector<Interval> &intervals, Interval &newInterval) {
+    if (intervals.empty()) return {newInterval};
+
+    vector<Interval> res;
+    int n = intervals.size(), i = 0;
+    for (; i < n && intervals[i][1] < newInterval[0]; i++) {
+      res.push_back(intervals[i]);
+    }
+
+    for (; i < n && newInterval[1] >= intervals[i][0]; i++) {
+      newInterval[0] = min(newInterval[0], intervals[i][0]);
+      newInterval[1] = max(newInterval[1], intervals[i][1]);
+    }
+
+    res.push_back(newInterval);
+
+    for (; i < n; i++) { res.push_back(intervals[i]); }
+
+    return res;
+  }
+};
diff --git a/README.md b/README.md
@@ -44,6 +44,7 @@ for solving problems.
 |  0054  |   Medium   | [Spiral Matrix](Problems/0054.cpp)                                                               |
 |  0055  |   Medium   | [Jump Game](Problems/0055.cpp)                                                                   |
 |  0056  |   Medium   | [Merge Intervals](Problems/0056.cpp)                                                             |
+|  0057  |   Medium   | [Insert Interval](Problems/0057.cpp)                                                             |
 |  0059  |   Medium   | [Spiral Matrix II](Problems/0059.cpp)                                                            |
 |  0061  |   Medium   | [Rotate List](Problems/0061.cpp)                                                                 |
 |  0066  |    Easy    | [Plus One](Problems/0066.cpp)                                                                    |