Two Easy O(n) C++ Solutions with Explanations
By far the best solution I have seen is of O(n) time (some solutions claim to be of O(logn) turns out to be O(n)). One of the simplest ideas is to compare each 
By far the best solution I have seen is of `O(n)` time (some solutions claim to be of `O(logn)` turns out to be `O(n)`). One of the simplest ideas is to compare each interval in `intervals` (`intervals[i]`) with `newInterval` and then perform respective operations according to their relationships.\n\n 1. If they overlap, merge them to `newInterval`;\n 2. If `intervals[i]` is to the left of `newInterval`, push `intervals[i]` to the result vector;\n 3. If `newInterval` is to the left of `intervals[i]`, push `newInterval` and all the remaining intervals (`intervals[i]`, ..., `intervals[n - 1]`) to the result vector.\n\nThe code is as follows. \n\n    class Solution {\n    public:\n        vector<Interval> insert(vector<Interval>& intervals, Interval newInterval) {\n            vector<Interval> res;\n            int n = intervals.size();\n            for (int i = 0; i < n; i++) {\n                if (intervals[i].end < newInterval.start)\n                    res.push_back(intervals[i]);\n                else if (newInterval.end < intervals[i].start) {\n                    res.push_back(newInterval);\n                    for (int j = i; j < n; j++)\n                        res.push_back(intervals[j]);\n                    return res; \n                }\n                else newInterval = merge(intervals[i], newInterval);\n            }\n            res.push_back(newInterval);\n            return res;\n        }\n    private:\n        Interval merge(Interval& interval1, Interval& interval2) {\n            int start = min(interval1.start, interval2.start);\n            int end = max(interval1.end, interval2.end);\n            return Interval(start, end);\n        }\n    };\n\nAnother idea is to search for the two ends of the overlapping intervals using binary search. Then we only need to merge `newInterval` with the intervals at the two ends if they overlap. All the intervals within the two ends will be contained in` newInterval`.\n\nLet's do the example in the problem statement: `intervals = [1, 2], [3, 5], [6, 7], [8, 10], [12, 16]` and `newInterval = [4, 9]`. We first find the rightmost interval with `start` smaller than that of `newInterval`, which is `[3, 5]`. Then we find the leftmost interval with `end` larger than that of `newInterval`, which is `[8, 10]`. Then all the intervals between them will be contained within `newInterval` (you may check this to convince yourself) and so can be safely ignored. We only need to check whether `newInterval` overlaps with the two intervals on the two ends and merge them if necessary.\n\nThe complete code is as follows.\n\n    class Solution {\n    public:\n        vector<Interval> insert(vector<Interval>& intervals, Interval newInterval) {\n            int n = intervals.size(), leftEnd, rightEnd, l, r;\n            vector<Interval> res;\n            // Find the rightmost interval with start smaller than that of newInterval\n            for (l = 0, r = n - 1; l <= r; ) {\n                int mid = l + ((r - l) >> 1);\n                if (intervals[mid].start > newInterval.start)\n                    r = mid - 1;\n                else l = mid + 1;\n            } \n            leftEnd = r;\n            // Find the leftmost interval with end larger than that of newInterval\n            for (l = 0, r = n - 1; l <= r; ) {\n                int mid = l + ((r - l) >> 1);\n                if (intervals[mid].end < newInterval.end)\n                    l = mid + 1;\n                else r = mid - 1;\n            }\n            rightEnd = l;\n            // Merge newInterval with intervals[leftEnd] and intervals[rightEnd] if necessary\n            if (leftEnd >= 0 && intervals[leftEnd].end >= newInterval.start)\n                newInterval.start = intervals[leftEnd--].start;\n            if (rightEnd < n && intervals[rightEnd].start <= newInterval.end)\n                newInterval.end = intervals[rightEnd++].end;\n            // Save the intervals sequentially\n            for (int i = 0; i <= leftEnd; i++)\n                res.push_back(intervals[i]);\n            res.push_back(newInterval);\n            for (int i = rightEnd; i < n; i++)\n                res.push_back(intervals[i]);\n            return res;\n        }\n    };
['C++']