Skip to content

57. Insert Interval 👍

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
 public:
  vector<vector<int>> insert(vector<vector<int>>& intervals,
                             vector<int>& newInterval) {
    const int n = intervals.size();
    vector<vector<int>> ans;
    int i = 0;

    while (i < n && intervals[i][1] < newInterval[0])
      ans.push_back(intervals[i++]);

    // Merge overlapping intervals.
    while (i < n && intervals[i][0] <= newInterval[1]) {
      newInterval[0] = min(newInterval[0], intervals[i][0]);
      newInterval[1] = max(newInterval[1], intervals[i][1]);
      ++i;
    }

    ans.push_back(newInterval);

    while (i < n)
      ans.push_back(intervals[i++]);

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
  public int[][] insert(int[][] intervals, int[] newInterval) {
    final int n = intervals.length;
    List<int[]> ans = new ArrayList<>();
    int i = 0;

    while (i < n && intervals[i][1] < newInterval[0])
      ans.add(intervals[i++]);

    // Merge overlapping intervals.
    while (i < n && intervals[i][0] <= newInterval[1]) {
      newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
      newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
      ++i;
    }

    ans.add(newInterval);

    while (i < n)
      ans.add(intervals[i++]);

    return ans.toArray(int[][] ::new);
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
  def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
    n = len(intervals)
    ans = []
    i = 0

    while i < n and intervals[i][1] < newInterval[0]:
      ans.append(intervals[i])
      i += 1

    # Merge overlapping intervals.
    while i < n and intervals[i][0] <= newInterval[1]:
      newInterval[0] = min(newInterval[0], intervals[i][0])
      newInterval[1] = max(newInterval[1], intervals[i][1])
      i += 1

    ans.append(newInterval)

    while i < n:
      ans.append(intervals[i])
      i += 1

    return ans