# LeetCode 435. Non-overlapping Intervals

2018/03/02 08:16

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:

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

Draw with some simple examples and find routine.

Sort based on ending point. Have max initialized as intervals end.

Starting from 2nd, if current interval start is smaller than max, there is overlap, res++.

Otherwise, there is no overlap, we update the maximum.

Time Complexity: O(nlogn). n = intervals.length.

Space: O(1).

AC Java:

 1 class Solution {
2     public int eraseOverlapIntervals(int[][] intervals) {
3         if(intervals == null || intervals.length < 2){
4             return 0;
5         }
6
7         Arrays.sort(intervals, (a, b) -> a == b ? b - a : a - b);
8         int max = intervals;
9         int res = 0;
10
11         for(int i = 1; i<intervals.length; i++){
12             if(intervals[i] < max){
13                 res++;
14             }else{
15                 max = intervals[i];
16             }
17         }
18
19         return res;
20     }
21 }

0
0 收藏

### 作者的其它热门文章 0 评论
0 收藏
0   