Simple C++ | Beats 99% | with Explanation
Intuition\n Describe your first thoughts on how to solve this problem. \nFirst of all if we think of approach so we can do this by using linear search or Binary
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nFirst of all if we think of approach so we can do this by using linear search or Binary search . So we know  Bianry search has logn timpecomplexity but through binary search we find where to insert in logn but we have to merge with others and insert also that will take O(n) so there is no need of binary search we can do a linear serach as well beacuse both will be O(n).\n# Approach\n<!-- Describe your approach to solving the problem. -->\nComing to Approach first we can think of many conditions but We only need to check three conditions that are :\n- Insert those intervals who are not overlapping and are less than our new Interval \n- Now check if our new Interval is overalpping wiht any other interval(s) so either insert if not overlapping or merge if overallping with others\n- Now insert those who are left i.e those intervals which are greater than new Interval\n*These condtions can easily be checked using a while loop*\nFor second condition when the inertvals are overlapping we can do that by :\n` (a,b)  and (c,d) the  new interval: [min(a,c),max(b,d)]`\n# Complexity\n- Time complexity:O(n)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:O(n)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    vector<vector<int>> insert(vector<vector<int>>& inv, vector<int>& newI) {\n       vector<vector<int>>ans;\n       int n=inv.size();\n        int i=0;\n        // insert those intervals which are not overlapping and less than newInterval\n       while(i<n and inv[i][1]<newI[0]){\n           ans.push_back(inv[i++]);\n       }\n       // now insert the new Interval or merge the interval if neccessary\n\n       while(i<n and newI[1]>=inv[i][0]){\n           newI[0]=min(newI[0],inv[i][0]);\n           newI[1]=max(newI[1],inv[i][1]);\n           i++;\n       }\n       ans.push_back(newI);\n      // insert thse intervals which are left or greater than the newInterval\n      while(i<n ){\n          ans.push_back(inv[i++]);\n      }\n       return ans; \n    }\n};\n```\n**Please upVote If Found HelpFull \uD83D\uDD3C**
['Array', 'Two Pointers', 'Binary Search', 'Sorting', 'C++']