435. Non-overlapping Intervals.md

435. Non-overlapping Intervals

---

leetcode Daily Challenge on August 15th, 2020.

leetcode-cn Daily Challenge on December 31th, 2020.

---

Difficulty : Medium

Related Topics : Greedy

---

Given a collection of intervals, find the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.

Example 1:

Input: [[1,2],[2,3],[3,4],[1,3]]
Output: 1
Explanation: [1,3] can be removed and the rest of intervals are non-overlapping.

Example 2:

Input: [[1,2],[1,2],[1,2]]
Output: 2
Explanation: You need to remove two [1,2] to make the rest of intervals non-overlapping.

Example 3:

Input: [[1,2],[2,3]]
Output: 0
Explanation: You don't need to remove any of the intervals since they're already non-overlapping.

Note:

• You may assume the interval's end point is always bigger than its start point.
• Intervals like [1,2] and [2,3] have borders "touching" but they don't overlap each other.

---

Solution

• mine
  • Java

    • Runtime: 5 ms, faster than 25.57%, Memory Usage: 42.3 MB, less than 10.65% of Java online submissions

      // O(N*logN)time
      // O(N) or O(1)space depends on arrays.sort
      public int eraseOverlapIntervals(int[][] intervals) {
          if (intervals == null || intervals.length < 2) return 0;
          Arrays.sort(intervals, (o1, o2) -> o1[1] - o2[1]);
          int res = 0;
          int end = intervals[0][1];
          for (int i = 1; i < intervals.length; i++) {
              if (intervals[i][0] < end) {
                  res++;
              }else{
                 end = intervals[i][1];
              }
          }
          return res;
      }
      

    • Runtime: 1 ms, faster than 100.00%, Memory Usage: 38.8 MB, less than 88.74% of Java online submissions

      // O(N*logN)time
      // O(N)space
      public int eraseOverlapIntervals(int[][] intervals) {
          Arrays.sort(intervals, (a , b) -> a[0] - b[0]);
          LinkedList<int[]> list = new LinkedList<>();
          for(int i = 0; i < intervals.length; i++){
              if(list.size() == 0){
                  list.add(intervals[i]);
                  continue;
              }
              int[] last = list.getLast();
              if(intervals[i][0] < last[1]){
                  if(intervals[i][1] < last[1]){
                      list.removeLast();
                      list.add(intervals[i]);
                  }
              }else{
                  list.add(intervals[i]);
              }
          }
          return intervals.length - list.size();
      }
      

---

• the most votes

• Runtime: 5 ms, faster than 25.57%, Memory Usage: 42.3 MB, less than 10.65% of Java online submissions

  // O(N*logN)time
  // O(N) or O(1)space depends on arrays.sort
  public int eraseOverlapIntervals(int[][] intervals) {
      if (intervals.length == 0) return 0;
  
      Arrays.sort(intervals, (a, b) -> a[1] == b[1] ? b[0] - a[0] : a[1] - b[1]);
  
      int minErase = 0;
      int prevEnd = Integer.MIN_VALUE;
      for (int[] interval : intervals) {
          if (prevEnd > interval[0]) minErase++;
          else prevEnd = interval[1];
      }
  
      return minErase;
  }
  

---