[C++/Java/Python] Short & Crisp Approach ✅
Approach:\n The approach used is to first iterate through the given intervals, and keeping track of the index of the interval where the new interval should be i
**Approach:**\n* The approach used is to `first` iterate through the given intervals, and keeping track of the index of the interval where the new `interval` should be inserted such that the intervals remain `sorted`. Then it will `merge` any overlapping intervals with the new interval and update its `start` and `end` times. `Finally`, it will insert the new interval into the correct position in the intervals and `return` the modified intervals.\n* The `key` idea behind this approach is to maintain the `sorted` order of the intervals, and to `merge` any overlapping intervals with the new interval. \n* By iterating through the intervals and keeping track of the index where the new interval should be `inserted`, we can ensure that the intervals `remain` sorted, and by merging any `overlapping` intervals with the new interval, we can ensure that the final `output` has no `overlapping` intervals.\n\n**C++:**\n```\nclass Solution {\npublic:\n    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {\n        vector<vector<int>> res;\n        int i = 0, n = intervals.size();\n        while (i < n && intervals[i][1] < newInterval[0]) res.push_back(intervals[i++]);\n        while (i < n && intervals[i][0] <= newInterval[1]) newInterval = {min(intervals[i][0], newInterval[0]), max(intervals[i][1], newInterval[1])}, i++;\n        res.push_back(newInterval);\n        while (i < n) res.push_back(intervals[i++]);\n        return res;\n    }\n};\n```\n**Java:**\n```\nclass Solution {\n    public int[][] insert(int[][] intervals, int[] newInterval) {\n        List<int[]> res = new ArrayList<>();\n        int i = 0, n = intervals.length;\n        while (i < n && intervals[i][1] < newInterval[0]) res.add(intervals[i++]);\n        while (i < n && intervals[i][0] <= newInterval[1]) newInterval = new int[] {Math.min(intervals[i][0], newInterval[0]), Math.max(intervals[i][1], newInterval[1])}, i++;\n        res.add(newInterval);\n        while (i < n) res.add(intervals[i++]);\n        return res.toArray(new int[res.size()][2]);\n    }\n}\n```\n**Python:**\n\n```\nclass Solution:\n    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:\n        res = []\n        i = 0\n        n = len(intervals)\n        while i < n and intervals[i][1] < newInterval[0]:\n            res.append(intervals[i])\n            i += 1\n        while i < n and intervals[i][0] <= newInterval[1]:\n            newInterval[0] = min(intervals[i][0], newInterval[0])\n            newInterval[1] = max(intervals[i][1], newInterval[1])\n            i += 1\n        res.append(newInterval)\n        while i < n:\n            res.append(intervals[i])\n            i += 1\n        return res\n```\n\n----\nThe **Time complexity** is **O(n)** \nThe **Space complexity** is **O(n)** .\n\n----\n\n\n
['C', 'Python', 'Java']