Merge & insert vs binary search & insert||3ms Beats 99.64%
Intuition\n Describe your first thoughts on how to solve this problem. \n2 different kinds of solutions are provided.\n1 is a transverse & insert the intervals 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n2 different kinds of solutions are provided.\n1 is a transverse & insert the intervals in the right places for the non-overlapping intervals; merging the intervals for the overlapping intervals.\n\n2nd approach uses binary search to find the real new interval ends, and insert the intervals without overlapping with the new one.\n# Approach\n<!-- Describe your approach to solving the problem. -->\nLet \'s see the approach using binary search for the testcase `intervals =\n[[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval =\n[4,8]`\nThe searching results are\n```\nleft=1, a=3\nright=4, b=10\noutput=[[1,2],[3,10],[12,16]]\n```\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$O(n)$\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$O(1)$\n# Code merge & insert||3ms Beats 99.64%\n```\n#pragma GCC optimize("O3", "unroll-loops")\nclass Solution {\npublic:\n    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) \n    {\n        vector<vector<int>> ans;\n        int a=newInterval[0], b=newInterval[1];\n        int i=0, n=intervals.size();\n        \n        // Insert intervals before the new interval or non-overlapping intervals\n        for ( ; i < n && intervals[i][1]<a; i++) \n            ans.push_back(intervals[i]);\n        \n        \n        // Merge overlapping intervals\n        for ( ; i < n && intervals[i][0] <= b; i++) {\n            a = min(a, intervals[i][0]);\n            b = max(b, intervals[i][1]);    \n        }\n        \n        ans.push_back({a, b}); // Insert the merged interval\n        \n        // Insert the remaining intervals\n        ans.reserve(ans.size()+intervals.size()-i);\n        ans.insert(ans.end(), intervals.begin()+i, intervals.end());\n\n        return ans;\n    }\n};\n\n\n```\n# C++ code using binary search twice & insert|||3ms Beats 99.64%\n```\n#pragma GCC optimize("O3", "unroll-loops")\nclass Solution {\npublic:\n    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) \n    {\n        int a=newInterval[0], b=newInterval[1];\n        int i=0, n=intervals.size();\n       \n        int left=lower_bound(intervals.begin(), intervals.end(), vector<int>({a, a}))-intervals.begin();\n        if (left!=0 && a<=intervals[left-1][1]) {\n            a=intervals[left-1][0];\n            left--;\n        }  \n    //    cout<<"left="<<left<<", a="<<a<<endl;   \n        int right=upper_bound(intervals.begin()+left, intervals.end(), \n        vector<int>({b, b}), [&](const vector<int>& x, const vector<int>&y){\n            return x[1]<y[1];\n        })-intervals.begin();\n        if (right<n && b >= intervals[right][0]){\n            b=intervals[right][1];\n            right++;\n        }\n    //   cout<<"right="<<right<<", b="<<b<<endl;\n        vector<vector<int>> ans;\n        ans.reserve(n-(right-left)+1);\n        ans.insert(ans.end(), intervals.begin(), intervals.begin()+left);\n        ans.push_back({a, b});\n        ans.insert(ans.end(), intervals.begin()+right, intervals.end());\n        return ans;\n    }\n};\n\n```\n
['Array', 'Binary Search', 'C++']