In this approach, we'll first identify where the new interval should be inserted to maintain order. After insertion, we'll iterate over the array and merge overlapping intervals.
Time Complexity: O(n), where n is the number of intervals.
Space Complexity: O(n) due to the allocation for the result.
1using System;
2using System.Collections.Generic;
3public class Solution {
4 public int[][] Insert(int[][] intervals, int[] newInterval) {
5 List<int[]> result = new List<int[]>();
6 int i = 0;
7 while (i < intervals.Length && intervals[i][1] < newInterval[0])
8 result.Add(intervals[i++]);
9 while (i < intervals.Length && intervals[i][0] <= newInterval[1]) {
10 newInterval[0] = Math.Min(newInterval[0], intervals[i][0]);
11 newInterval[1] = Math.Max(newInterval[1], intervals[i][1]);
12 i++;
13 }
14 result.Add(newInterval);
15 while (i < intervals.Length)
16 result.Add(intervals[i++]);
17 return result.ToArray();
18 }
19}C#'s solution mirrors the logic seen in Python and Java, utilizing a List to manage result construction because Lists allow for dynamic resizing unlike standard arrays.
This approach optimizes finding the insert position using binary search. After inserting the new interval, it merges overlapping intervals. This is slightly more efficient when the intervals list is large.
Time Complexity: O(n), even with binary search (O(log n) for insertion, O(n) for merging).
Space Complexity: O(n), to store the new list of intervals.
1def insert(intervals, newInterval):
2 def find_position(arr, target):
3 low, high = 0, len(arr)
4 while low < high:
5 mid = (low + high) // 2
6 if arr[mid][0] < target:
7 low = mid + 1
8 else:
9 high = mid
10 return low
11
12 pos = find_position(intervals, newInterval[0])
13 intervals.insert(pos, newInterval)
14 merged = [intervals[0]]
15 for i in range(1, len(intervals)):
16 if merged[-1][1] >= intervals[i][0]:
17 merged[-1][1] = max(merged[-1][1], intervals[i][1])
18 else:
19 merged.append(intervals[i])
20 return merged
21The Python approach combines binary search for efficient insertion with a concise method for merging intervals by positioning and combining correctly pre-sorted intervals quickly.