【Video】2 solutions + Bonus
Intuition\nThink about start and end when they are overlapping.\n\n---\n\n# Solution Video\n\nhttps://youtu.be/LpRqRbH4itk\n\n### \u2B50\uFE0F\u2B50\uFE0F Don\'
# Intuition\nThink about start and end when they are overlapping.\n\n---\n\n# Solution Video\n\nhttps://youtu.be/LpRqRbH4itk\n\n### \u2B50\uFE0F\u2B50\uFE0F Don\'t forget to subscribe to my channel! \u2B50\uFE0F\u2B50\uFE0F\n\n**\u25A0 Subscribe URL**\nhttp://www.youtube.com/channel/UC9RMNwYTL3SXCP6ShLWVFww?sub_confirmation=1\n\nSubscribers: 10,205\nThank you for your support!\n\n---\n\n# Solution 1\n\n```\nintervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]\n```\nSimply, add a new interval to intervals, then sort them with start time.\n```\n[[1,2],[3,5],[4,8],[6,7],[8,10],[12,16]]\n```\nAfter that, it\'s the same as merge interval quesiton. I put my video here.\n\nhttps://youtu.be/DAppffTClNQ\n\nCreate return variable `res` initialized with the first interval\n\n```\nres = [1,2]\n```\nThen iterate through from index `1`. if end time of the last interval in `res` is greater than start time of current interval, we should merge them by comparing max end times.\n\nLet\'s see how it works.\n\n```\n         \u2193\n[[1,2],[3,5],[4,8],[6,7],[8,10],[12,16]]\nres = [[1,2]]\n\nif 2 >= 3 \u2192 false, that means no overlapping.\n\nres = [[1,2],[3,5]]\n```\n```\n               \u2193\n[[1,2],[3,5],[4,8],[6,7],[8,10],[12,16]]\nres = [[1,2],[3,5]]\n\nif 5 >= 4 \u2192 true, that means overlapping. Compare end time.\n\nres = [[1,2],[3,5]]\n```\nIn this case, start time will not be updated **because we know that input array is sorted in ascending order.** Previous interval definitely has small start time.\n\nLet\'s comapre end time.\n```\nmax(5,8)\n= 8\n\nres = [[1,2],[3,8]]\n\n       | merged  |\n[[1,2],[3,5],[4,8],[6,7],[8,10],[12,16]]\n```\nLet\'s continue.\n```\n                     \u2193\n[[1,2],[3,5],[4,8],[6,7],[8,10],[12,16]]\nres = [[1,2],[3,8]]\n\nif 8 >= 6 \u2192 true, that means overlapping. Compare end time.\n\nmax(8,7)\n= 8\n\nres = [[1,2],[3,8]]\n\n       |     merged    |\n[[1,2],[3,5],[4,8],[6,7],[8,10],[12,16]]\n```\n\n```\n                           \u2193\n[[1,2],[3,5],[4,8],[6,7],[8,10],[12,16]]\nres = [[1,2],[3,8]]\n\nif 8 >= 8 \u2192 true, that means overlapping. Compare end time.\n\nmax(8,10)\n= 10\n\nres = [[1,2],[3,10]]\n\n       |     merged           |\n[[1,2],[3,5],[4,8],[6,7],[8,10],[12,16]]\n```\n```\n                                   \u2193\n[[1,2],[3,5],[4,8],[6,7],[8,10],[12,16]]\nres = [[1,2],[3,10]]\n\nif 10 >= 12 \u2192 false, that means no overlapping.\n\nres = [[1,2],[3,10],[12,16]]\n\n       |     merged           |\n[[1,2],[3,5],[4,8],[6,7],[8,10],[12,16]]\n```\n\n```\nreturn [[1,2],[3,10],[12,16]]\n```\n\n---\n\nhttps://youtu.be/bU_dXCOWHls\n\n---\n\n# Complexity\n- Time complexity: $$O(n log n)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(sort)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n```python []\nclass Solution:\n    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:\n        intervals.append(newInterval)\n        intervals.sort()\n\n        res = [intervals[0]]\n\n        for i in range(1, len(intervals)):\n            if res[-1][1] >= intervals[i][0]:\n                res[-1][1] = max(res[-1][1], intervals[i][1])\n            else:\n                res.append(intervals[i])\n\n        return res\n```\n```javascript []\nvar insert = function(intervals, newInterval) {\n    intervals.push(newInterval);\n    intervals.sort((a, b) => a[0] - b[0]);\n\n    let res = [intervals[0]];\n\n    for (let i = 1; i < intervals.length; i++) {\n        if (res[res.length - 1][1] >= intervals[i][0]) {\n            res[res.length - 1][1] = Math.max(res[res.length - 1][1], intervals[i][1]);\n        } else {\n            res.push(intervals[i]);\n        }\n    }\n\n    return res;    \n};\n```\n```java []\nclass Solution {\n    public int[][] insert(int[][] intervals, int[] newInterval) {\n       List<int[]> intervalList = new ArrayList<>(Arrays.asList(intervals));\n        intervalList.add(newInterval);\n        Collections.sort(intervalList, (a, b) -> Integer.compare(a[0], b[0]));\n\n        List<int[]> res = new ArrayList<>();\n        int[] current = intervalList.get(0);\n\n        for (int i = 1; i < intervalList.size(); i++) {\n            int[] interval = intervalList.get(i);\n            \n            if (current[1] >= interval[0]) {\n                current[1] = Math.max(current[1], interval[1]);\n            } else {\n                res.add(current);\n                current = interval;\n            }\n        }\n\n        res.add(current);\n        return res.toArray(new int[res.size()][]);\n    }\n}\n```\n```C++ []\nclass Solution {\npublic:\n    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {\n        intervals.push_back(newInterval);\n        sort(intervals.begin(), intervals.end());\n\n        vector<vector<int>> res;\n        res.push_back(intervals[0]);\n\n        for (int i = 1; i < intervals.size(); ++i) {\n            if (res.back()[1] >= intervals[i][0]) {\n                res.back()[1] = max(res.back()[1], intervals[i][1]);\n            } else {\n                res.push_back(intervals[i]);\n            }\n        }\n\n        return res;        \n    }\n};\n```\n\n# Step by Step Algorithm\n\n### Step 1\n```python\nintervals.append(newInterval)\n```\n**Explanation**: This line appends `newInterval` to the list `intervals`. By doing this, we add the new interval into the list to handle it like the other intervals.\n\n### Step 2\n```python\nintervals.sort()\n```\n**Explanation**: This line sorts the `intervals` list in ascending order based on the starting times of each interval. Sorting allows us to process overlapping intervals in order, making it easier to merge them.\n\n### Step 3\n```python\nres = [intervals[0]]\n```\n**Explanation**: Here, we initialize a result list `res` with the first interval from the sorted `intervals` list. This list will store the merged intervals.\n\n### Step 4\n```python\nfor i in range(1, len(intervals)):\n```\n**Explanation**: This line starts a loop from the second interval (`i = 1`) to the last interval in `intervals`. The purpose of the loop is to iterate over each interval and merge any overlapping intervals.\n\n### Step 5\n```python\nif res[-1][1] >= intervals[i][0]:\n```\n**Explanation**: This line checks if the last interval in `res` overlaps with the current interval (`intervals[i]`). If the end of the last interval in `res` (`res[-1][1]`) is greater than or equal to the start of the current interval (`intervals[i][0]`), then there is an overlap.\n\n### Step 6\n```python\nres[-1][1] = max(res[-1][1], intervals[i][1])\n```\n**Explanation**: When the intervals overlap, this line merges them by updating the end of the last interval in `res` to be the maximum of its current end and the end of the current interval. This ensures that `res[-1]` covers both intervals.\n\n### Step 7\n```python\nelse:\n    res.append(intervals[i])\n```\n**Explanation**: If there is no overlap, this line adds the current interval (`intervals[i]`) as a new entry in `res` since it doesn\u2019t merge with the previous intervals.\n\n### Step 8\n```python\nreturn res\n```\n**Explanation**: Finally, the function returns `res`, which now contains all the intervals after merging any overlapping intervals. This is the desired output.\n\n---\n\n# Solution 2\n\n```\nintervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]\n```\nIn solution 2, we try to find a place where we should insert new interval. To do that, **we compare end time of current interval with start time of new interval.**\n```\nend time of current < start time new\n\n   \u2193\n[[1,2],[3,5],[6,7],[8,10],[12,16]]\n= 2 < 4 \u2192 true\n\nres = [[1,2]]\n\n         \u2193\n[[1,2],[3,5],[6,7],[8,10],[12,16]]\n= 5 < 4 \u2192 false, we found a place to insert new interval.\n```\n\nIn the second step, compare start time of current interval with end time of new interval to comfirm current two intervals are overlapping each other.\n\n---\n\n\u2B50\uFE0F Points\n\n- Why we check the second step?\n\nSomebody is wondering why we check the step step because we already checked they are overlapping in the first step.\n\nThe answer is there is possiblity that we have multiple intervals after current interval.\n\nIf we definitely know current interval is the last, we don\'t have to check it but look at input array. We will start to merge `[3,5]` and `[4,8]`, but we still have `3` intervals after `[3,5]`.\n\nIn that case, we have to comcpare start time of current interval with end of the last interval in `res`.\n\nThat\'s why we need the second step.\n\n---\nIf the second step, the condition below is true, we will update start and end time of new interval.\n\n```\nstart time of current interval <= end time of new interval\n```\n```\n                     \u2193\nintervals = [[1,2],[3,5],[6,7],[8,10],[12,16]]\nnewInterval = [4,8]\n\n= 3 <= 8 \u2192 true\n```\nIn this case, we will update newInterval. Start time and end time should be\n\n```\nstart = min(start time of new, start time of current)\nend = max(end time of new, end time of current)\n```\nwe want the widest range if we merge multiple intervals, that\'s why start time should be minimum number and end time should be maximum number.\n\n```\n                     \u2193\nintervals = [[1,2],[3,5],[6,7],[8,10],[12,16]]\nnewInterval = [4,8]\n\n= 3 <= 8 \u2192 true\n\nnewInterval[0] = min(4, 3)\nnewInterval[1] = max(8, 5)\nnewInterval = [3,8]\n```\nWe continue until we don\'t meet\n```\nstart time of current interval <= end time of new interval\n```\n```\nres = [[1,2]]\n\n                           \u2193\nintervals = [[1,2],[3,5],[6,7],[8,10],[12,16]]\nnewInterval = [3,8]\n\n= 6 <= 8 \u2192 true, they are overlapping\n\nnewInterval[0] = min(3, 6)\nnewInterval[1] = max(8, 7)\nnewInterval = [3,8]\n----------------------------------------------------------\n                                 \u2193\nintervals = [[1,2],[3,5],[6,7],[8,10],[12,16]]\nnewInterval = [3,8]\n\n= 8 <= 8 \u2192 true, they are overlapping\n\nnewInterval[0] = min(3, 8)\nnewInterval[1] = max(8, 10)\nnewInterval = [3,10]\n----------------------------------------------------------\n                                         \u2193\nintervals = [[1,2],[3,5],[6,7],[8,10],[12,16]]\nnewInterval = [3,10]\n\n= 12 <= 10 \u2192 false, they are not overlapping\n```\nIn that case, we break the second loop and add the new interval.\n```\nres = [[1,2],[3,10]]\n```\nAfter that, all we have to do is add rest of intervals which is `[12,16]`.\n\n```\nreturn [[1,2],[3,10],[12,16]]\n```\n\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\n```python []\nclass Solution:\n    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:\n        n = len(intervals)\n        res = []\n\n        i = 0\n        while i < n and intervals[i][1] < newInterval[0]:\n            res.append(intervals[i])\n            i += 1\n\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\n        res.append(newInterval)\n        res.extend(intervals[i:])\n\n        return res\n```\n```javascript []\nvar insert = function(intervals, newInterval) {\n    const n = intervals.length;\n    const res = [];\n    \n    let i = 0;\n    while (i < n && intervals[i][1] < newInterval[0]) {\n        res.push(intervals[i]);\n        i++;\n    }\n\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\n    res.push(newInterval);\n    res.push(...intervals.slice(i));\n\n    return res;    \n};\n```\n```java []\nclass Solution {\n    public int[][] insert(int[][] intervals, int[] newInterval) {\n       int n = intervals.length;\n        List<int[]> res = new ArrayList<>();\n\n        int i = 0;\n        while (i < n && intervals[i][1] < newInterval[0]) {\n            res.add(intervals[i]);\n            i++;\n        }\n\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\n        res.add(newInterval);\n\n        while (i < n) {\n            res.add(intervals[i]);\n            i++;\n        }\n\n        return res.toArray(new int[res.size()][]);\n    }\n}\n```\n```C++ []\nclass Solution {\npublic:\n    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {\n        int n = intervals.size();\n        vector<vector<int>> res;\n\n        int i = 0;\n        while (i < n && intervals[i][1] < newInterval[0]) {\n            res.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\n        res.push_back(newInterval);\n        while (i < n) {\n            res.push_back(intervals[i]);\n            i++;\n        }\n\n        return res;\n    }\n};\n```\n\n# Step by Step Algorithm\n\n```python\nn = len(intervals)\n```\n\n- **Explanation**: Calculate the total number of intervals and store it in `n`. This helps control the loop later when iterating through all intervals.\n\n```python\nres = []\n```\n\n- **Explanation**: Initialize an empty list `res` to store the final merged intervals.\n\n```python\ni = 0\nwhile i < n and intervals[i][1] < newInterval[0]:\n    res.append(intervals[i])\n    i += 1\n```\n\n- **Explanation**:\n  - **Condition**: Continue the loop while `i < n` and the end of the current interval (`intervals[i][1]`) is less than the start of `newInterval` (`newInterval[0]`).\n  - This part of the code adds all intervals that are completely before `newInterval` (no overlap) to `res`.\n  - **Action**: Each non-overlapping interval is added to `res`, and the index `i` is incremented.\n\n```python\nwhile 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```\n\n- **Explanation**:\n  - **Condition**: Continue the loop while `i < n` and the start of the current interval (`intervals[i][0]`) is less than or equal to the end of `newInterval` (`newInterval[1]`).\n  - This indicates overlapping intervals, so they need to be merged.\n  - **Action**: Update `newInterval` to merge with `intervals[i]` by adjusting:\n    - The start of `newInterval` to the minimum of the current start values.\n    - The end of `newInterval` to the maximum of the current end values.\n  - After merging, increment `i` to move to the next interval.\n\n```python\nres.append(newInterval)\n```\n\n- **Explanation**: Add the merged `newInterval` (containing all merged overlapping intervals) to `res`.\n\n```python\nres.extend(intervals[i:])\n```\n\n- **Explanation**: Add any remaining intervals after `newInterval` (which are not overlapping) directly to `res`.\n\n```python\nreturn res\n```\n\n- **Explanation**: Return `res`, which now contains all intervals, including the newly inserted interval, with all overlapping intervals merged.\n\n---\n\n\n# Bonus\n\nWhat if we want to solve this question with one loop? How do you rewrite your code?\n\n```python []\nclass Solution:\n    def insert(self, intervals: list[list[int]], newInterval: list[int]) -> list[list[int]]:\n        res = []\n\n        for interval in intervals:\n            if newInterval[1] < interval[0]:\n                res.append(newInterval)\n                newInterval = interval\n            elif newInterval[0] > interval[1]:\n                res.append(interval)\n            else:\n                newInterval[0] = min(newInterval[0], interval[0])\n                newInterval[1] = max(newInterval[1], interval[1])\n\n        res.append(newInterval)\n        return res\n```\n```javascript []\nvar insert = function(intervals, newInterval) {\n    const res = [];\n\n    for (const interval of intervals) {\n        if (newInterval[1] < interval[0]) {\n            res.push(newInterval);\n            newInterval = interval;\n        } else if (newInterval[0] > interval[1]) {\n            res.push(interval);\n        } else {\n            newInterval[0] = Math.min(newInterval[0], interval[0]);\n            newInterval[1] = Math.max(newInterval[1], interval[1]);\n        }\n    }\n\n    res.push(newInterval);\n    return res;    \n};\n```\n```java []\nclass Solution {\n    public int[][] insert(int[][] intervals, int[] newInterval) {\n        List<int[]> res = new ArrayList<>();\n\n        for (int[] interval : intervals) {\n            if (newInterval[1] < interval[0]) {\n                res.add(newInterval);\n                newInterval = interval;\n            } else if (newInterval[0] > interval[1]) {\n                res.add(interval);\n            } else {\n                newInterval[0] = Math.min(newInterval[0], interval[0]);\n                newInterval[1] = Math.max(newInterval[1], interval[1]);\n            }\n        }\n        \n        res.add(newInterval);\n        return res.toArray(new int[res.size()][]);\n    }\n}\n```\n```C++ []\nclass Solution {\npublic:\n    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {\n        vector<vector<int>> res;\n\n        for (const auto& interval : intervals) {\n            if (newInterval[1] < interval[0]) {\n                res.push_back(newInterval);\n                newInterval = interval;\n            } else if (newInterval[0] > interval[1]) {\n                res.push_back(interval);\n            } else {\n                newInterval[0] = min(newInterval[0], interval[0]);\n                newInterval[1] = max(newInterval[1], interval[1]);\n            }\n        }\n\n        res.push_back(newInterval);\n        return res;\n    }\n};\n```\n\n---\n\nThank you for reading my post.\n\n## \u2B50\uFE0F Subscribe URL\nhttp://www.youtube.com/channel/UC9RMNwYTL3SXCP6ShLWVFww?sub_confirmation=1\n\n## \u2B50\uFE0F Twitter\nhttps://twitter.com/CodingNinjaAZ\n\n## \u2B50\uFE0F Related Question - merge interval #56\n\nhttps://youtu.be/DAppffTClNQ
['C++', 'Java', 'Python3', 'JavaScript']