Skip to content

1272. Remove 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
class Solution {
 public:
  vector<vector<int>> removeInterval(vector<vector<int>>& intervals,
                                     vector<int>& toBeRemoved) {
    vector<vector<int>> ans;

    for (const vector<int>& interval : intervals) {
      const int a = interval[0];
      const int b = interval[1];
      if (a >= toBeRemoved[1] || b <= toBeRemoved[0]) {
        ans.push_back(interval);
      } else {  // a < toBeRemoved[1] && b > toBeRemoved[0]
        if (a < toBeRemoved[0])
          ans.push_back({a, toBeRemoved[0]});
        if (b > toBeRemoved[1])
          ans.push_back({toBeRemoved[1], b});
      }
    }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
  public List<List<Integer>> removeInterval(int[][] intervals, int[] toBeRemoved) {
    List<List<Integer>> ans = new ArrayList<>();

    for (int[] interval : intervals) {
      final int a = interval[0];
      final int b = interval[1];
      if (a >= toBeRemoved[1] || b <= toBeRemoved[0]) {
        ans.add(Arrays.asList(a, b));
      } else { // a < toBeRemoved[1] && b > toBeRemoved[0]
        if (a < toBeRemoved[0])
          ans.add(Arrays.asList(a, toBeRemoved[0]));
        if (b > toBeRemoved[1])
          ans.add(Arrays.asList(toBeRemoved[1], b));
      }
    }

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
  def removeInterval(self, intervals: List[List[int]], toBeRemoved: List[int]) -> List[List[int]]:
    ans = []

    for a, b in intervals:
      if a >= toBeRemoved[1] or b <= toBeRemoved[0]:
        ans.append([a, b])
      else:  # a < toBeRemoved[1] and b > toBeRemoved[0]
        if a < toBeRemoved[0]:
          ans.append([a, toBeRemoved[0]])
        if b > toBeRemoved[1]:
          ans.append([toBeRemoved[1], b])

    return ans