Simple traverse and insert at correct position
\n\n# Intuition\nMy initial thought to solve this problem is to iterate through the list of intervals and compare each interval with the new interval to determi
![Screenshot from 2024-03-17 07-25-19.png](https://assets.leetcode.com/users/images/52dab4d3-082e-41ba-88a4-7a73610546fc_1710640544.8754792.png)\n\n# Intuition\nMy initial thought to solve this problem is to iterate through the list of intervals and compare each interval with the new interval to determine its position for insertion.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nI will traverse through the list of intervals and compare each interval\'s start and end points with the start and end points of the new interval. Based on the comparison, I will insert the new interval appropriately, ensuring that the resulting list remains sorted and non-overlapping.\n# Complexity\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n- Time complexity: O(n), where n is the number of intervals in the input list. This is because we iterate through the list of intervals only once.\n\n- Space complexity: O(n) as well. We are using extra space to store the resultant list of intervals, which could potentially contain all intervals from the input list plus the new interval.\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```c++ []\nclass Solution {\npublic:\n    vector<vector<int>> insert(vector<vector<int>>& inv, vector<int>& ninv) {\n        vector<vector<int>>ans;\n        int start=ninv[0],end=ninv[1];\n        bool inserted=false;\n        for(int i=0;i<size(inv);i++){\n            int cstart=inv[i][0],cend=inv[i][1];\n            \n            if(cend<start || inserted){\n                ans.push_back({cstart,cend});\n                continue;\n            }\n            start=min(start,cstart);\n            if(end<cstart){\n                ans.push_back({start,end});\n                ans.push_back({cstart,cend});\n                inserted=true;\n                continue;\n            }\n            if(end<=cend){\n                ans.push_back({start,cend});\n                inserted=true;               \n            }\n        }\n        if(!inserted){\n            ans.push_back({start,end});\n        }\n         return ans;\n    }\n};\n```\n```python3 []\nclass Solution:\n    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:\n        ans = []\n        start, end = newInterval\n        \n        inserted = False\n        for inv in intervals:\n            cstart, cend = inv\n            \n            if cend < start or inserted:\n                ans.append([cstart, cend])\n                continue\n            \n            start = min(start, cstart)\n            if end < cstart:\n                ans.append([start, end])\n                ans.append([cstart, cend])\n                inserted = True\n                continue\n            \n            if end <= cend:\n                ans.append([start, cend])\n                inserted = True\n        \n        if not inserted:\n            ans.append([start, end])\n        \n        return ans\n\n```\n```java []\n\nclass Solution {\n    public int[][] insert(int[][] intervals, int[] newInterval) {\n        List<int[]> ans = new ArrayList<>();\n        int start = newInterval[0], end = newInterval[1];\n        boolean inserted = false;\n        \n        for (int[] inv : intervals) {\n            int cstart = inv[0], cend = inv[1];\n            \n            if (cend < start || inserted) {\n                ans.add(new int[]{cstart, cend});\n                continue;\n            }\n            \n            start = Math.min(start, cstart);\n            if (end < cstart) {\n                ans.add(new int[]{start, end});\n                ans.add(new int[]{cstart, cend});\n                inserted = true;\n                continue;\n            }\n            \n            if (end <= cend) {\n                ans.add(new int[]{start, cend});\n                inserted = true;\n            }\n        }\n        \n        if (!inserted) {\n            ans.add(new int[]{start, end});\n        }\n        \n        return ans.toArray(new int[ans.size()][]);\n    }\n}\n\n```\n\n\n
['Python', 'C++', 'Java']