Best Solution || Explanation || Step by Step || For Beginners ||
Intuition\nThe problem involves inserting a new interval into a sorted list of non-overlapping intervals and merging them if necessary. The key insight is that 
# Intuition\nThe problem involves inserting a new interval into a sorted list of non-overlapping intervals and merging them if necessary. The key insight is that since the intervals are already sorted by their start times, we can maintain this sorted order by iterating through the list and merging the new interval with any overlapping intervals. \n\nThere are three main phases:\n1. Add all intervals that are completely before the new interval (non-overlapping).\n2. Merge overlapping intervals with the new interval.\n3. Add all remaining intervals that are after the merged new interval.\n\nThis structure allows us to handle the problem efficiently in a single pass through the list.\n\n# Approach\n1. **Initialize an empty list `ans`** to store the resulting intervals.\n2. **Iterate through the original intervals**:\n   - First, add all intervals that end before the new interval starts. These intervals don\u2019t overlap with the new one, so they can be directly added to `ans`.\n   - Next, merge all intervals that overlap with the new interval. An interval overlaps if its start is less than or equal to the end of the new interval. We merge by updating the start of the new interval to the minimum start and the end of the new interval to the maximum end among the overlapping intervals.\n   - Finally, add all remaining intervals that start after the new interval ends.\n3. **Convert the resulting list of intervals** (in `ans`) back to a 2D array and return it.\n\n# Complexity\n- **Time complexity:**\n  - The time complexity is $$O(n)$$, where `n` is the number of intervals. This is because we only iterate through the list of intervals once, performing constant-time operations in each step.\n\n- **Space complexity:**\n  - The space complexity is also $$O(n)$$, as we are storing up to `n` intervals in the `ans` list. The input list does not get modified in place; instead, we create a new list for the result.\n\n# Detailed Explanation\n### Step-by-Step Walkthrough:\n1. **Phase 1: Add non-overlapping intervals (before the new interval)**\n   - We loop through the `intervals` list and check each interval. If the current interval ends before the new interval starts (`intervals[i][1] < newInterval[0]`), it means the current interval doesn\'t overlap with the new one. We simply add it to the result list `ans`.\n   \n2. **Phase 2: Merge overlapping intervals**\n   - Once we reach an interval that starts before or at the same time as the new interval ends, it means there\u2019s a potential overlap. We continue merging intervals as long as they overlap. For each overlapping interval, we update the start of the new interval to the minimum start of both intervals, and the end of the new interval to the maximum end.\n   \n3. **Phase 3: Add remaining non-overlapping intervals (after the new interval)**\n   - After we merge all overlapping intervals, the new merged interval is added to `ans`. Then, we add all remaining intervals that start after the new merged interval ends. These intervals also do not overlap with the new one, so they can be directly added to the result.\n\n### Edge Cases:\n1. **Empty Intervals:**\n   - If the input list `intervals` is empty, we simply return the new interval as the result.\n   \n2. **New Interval Before All:**\n   - If the new interval ends before any of the existing intervals start, it should be inserted at the beginning, and no merging is required.\n\n3. **New Interval After All:**\n   - If the new interval starts after all existing intervals end, it should be inserted at the end without merging.\n\n4. **Complete Overlap with All Intervals:**\n   - If the new interval overlaps with all the intervals, it will end up merging with all of them, and the final result will contain just one large interval.\n\n# Code\n```java []\nclass Solution {\n    public int[][] insert(int[][] intervals, int[] newInterval) {\n        List<int[]> ans = new ArrayList<>();\n        int n = intervals.length, i = 0;\n\n        // Add all intervals that come before the new interval\n        while (i < n && intervals[i][1] < newInterval[0]) {\n            ans.add(intervals[i]);\n            i++;\n        }\n\n        // Merge overlapping intervals\n        while (i < n && intervals[i][0] <= newInterval[1]) {\n            newInterval[0] = Math.min(newInterval[0], intervals[i][0]);\n            newInterval[1] = Math.max(newInterval[1], intervals[i][1]);\n            i++;\n        }\n        ans.add(newInterval);\n\n        // Add the remaining intervals\n        while (i < n) {\n            ans.add(intervals[i]);\n            i++;\n        }\n\n        // Convert the list of intervals back to a 2D array\n        return ans.toArray(new int[ans.size()][]);\n    }\n}\n```\n``` cpp []\nclass Solution {\npublic:\n    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {\n        vector<vector<int>> ans;\n        int n = intervals.size(), i = 0;\n\n        while(i < n && intervals[i][1] < newInterval[0]){\n            ans.push_back(intervals[i]);\n            i++;\n        }\n        \n        while(i < n && intervals[i][0] <= newInterval[1]){\n            newInterval[0] = min(newInterval[0], intervals[i][0]);\n            newInterval[1] = max(newInterval[1], intervals[i][1]);\n            i++;\n        }\n        ans.push_back(newInterval);\n\n        while(i < n){\n            ans.push_back(intervals[i]);\n            i++;\n        }\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        n = len(intervals)\n        i = 0\n\n        # Add all intervals that come before the new interval\n        while i < n and intervals[i][1] < newInterval[0]:\n            ans.append(intervals[i])\n            i += 1\n\n        # Merge overlapping intervals\n        while i < n and intervals[i][0] <= newInterval[1]:\n            newInterval[0] = min(newInterval[0], intervals[i][0])\n            newInterval[1] = max(newInterval[1], intervals[i][1])\n            i += 1\n        ans.append(newInterval)\n\n        # Add the remaining intervals\n        while i < n:\n            ans.append(intervals[i])\n            i += 1\n\n        return ans\n```
['Array', 'C++', 'Java', 'Python3']