Simple One Pass Solution | Explained
Approach\nThe algorithm merges a new interval into a list of sorted, non-overlapping intervals. It iterates through the list of intervals while considering thre
# Approach\nThe algorithm merges a new interval into a list of sorted, non-overlapping intervals. It iterates through the list of intervals while considering three possible scenarios for each interval in relation to the new interval:\n\n1. **Non-overlapping before the new interval**: If the current interval ends before the new interval starts, it\'s added to the result list as is.\n2. **Non-overlapping after the new interval**: If the current interval starts after the new interval ends, this indicates that all possible merges have been done. The new interval is added to the result list, and the current interval becomes the next new interval to consider.\n3. **Overlapping intervals**: If the current interval overlaps with the new interval (i.e., the current interval starts before the new interval ends or ends after the new interval starts), the intervals are merged. This is done by updating the start of the new interval to the minimum start of both intervals and the end to the maximum end of both.\n\nThis process is repeated for each interval in the list. After iterating through all intervals, the last version of the new interval (which might have been merged with several intervals in the list) is added to the result. This ensures that all overlapping intervals are merged into a single interval, and all non-overlapping intervals are kept intact.\n\n# Complexity\n- Time complexity:\nThe time complexity of this algorithm is **O(N)**, where **N** is the number of intervals in the input list. This efficiency arises because the algorithm iterates through the list of intervals exactly once. Each interval is considered once and is either added to the result list directly or merged with the new interval, which is also a constant time operation.\n\n- Space complexity:\nThe space complexity is **O(1)**. Apart from the space required for the output, the algorithm uses a constant amount of space for variables such as loop counters and temporary variables to store interval bounds during merging (i.e., the start and end of the new interval being merged). This space does not scale with the input size and is thus considered O(1).\n\n# Code\n```\nclass Solution {\n    public int[][] insert(int[][] intervals, int[] newInterval) {\n        List<int[]> mergedIntervals = new ArrayList<>();\n\n        for (int[] interval : intervals) {\n            \n            // Before the new interval\n            if (interval[1] < newInterval[0]) {\n                mergedIntervals.add(interval);\n            } \n            // After the new interval\n            else if (interval[0] > newInterval[1]) {\n                mergedIntervals.add(newInterval);\n                newInterval = interval; // Update newInterval to current, as it will be added in order afterwards\n            } \n            // Overlapping intervals\n            else {\n                // Merge with newInterval by updating its start and end as needed\n                newInterval[0] = Math.min(newInterval[0], interval[0]);\n                newInterval[1] = Math.max(newInterval[1], interval[1]);\n            }\n        }\n\n        // Add the last interval, which is either the original newInterval or the one merged with others\n        mergedIntervals.add(newInterval);\n\n        return mergedIntervals.toArray(new int[mergedIntervals.size()][2]);\n    }\n}\n\n```
['Java']