44
55import java .util .Arrays ;
66import java .util .Collections ;
7- import java .util .Comparator ;
87
9- /**Given a collection of intervals, find the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.
8+ /**
9+ * 435. Non-overlapping Intervals
10+ *
11+ * Given a collection of intervals,
12+ * find the minimum number of intervals you need to remove to make the rest of the
13+ * intervals non-overlapping.
1014
1115 Note:
1216 You may assume the interval's end point is always bigger than its start point.
1317 Intervals like [1,2] and [2,3] have borders "touching" but they don't overlap each other.
18+
1419 Example 1:
1520 Input: [ [1,2], [2,3], [3,4], [1,3] ]
16-
1721 Output: 1
18-
1922 Explanation: [1,3] can be removed and the rest of intervals are non-overlapping.
23+
2024 Example 2:
2125 Input: [ [1,2], [1,2], [1,2] ]
22-
2326 Output: 2
24-
2527 Explanation: You need to remove two [1,2] to make the rest of intervals non-overlapping.
28+
2629 Example 3:
2730 Input: [ [1,2], [2,3] ]
28-
2931 Output: 0
30-
31- Explanation: You don't need to remove any of the intervals since they're already non-overlapping. */
32+ Explanation: You don't need to remove any of the intervals since they're already non-overlapping.
33+ */
3234
3335public class _435 {
3436
35- /**
36- * References:: https://discuss.leetcode.com/topic/65828/java-solution-with-clear-explain
37- * and https://discuss.leetcode.com/topic/65594/java-least-is-most
38- * Sort the intervals by their end time, if equal, then sort by their start time.
39- */
40- public static int eraseOverlapIntervals (Interval []intervals ) {
41- Collections .sort (Arrays .asList (intervals ),new Comparator <Interval >() {
42- @ Override
43- public int compare (Interval o1 ,Interval o2 ) {
37+ public static class Solution1 {
38+ /**
39+ * credit:: https://discuss.leetcode.com/topic/65828/java-solution-with-clear-explain
40+ * and https://discuss.leetcode.com/topic/65594/java-least-is-most
41+ * Sort the intervals by their end time, if equal, then sort by their start time.
42+ */
43+ public int eraseOverlapIntervals (Interval []intervals ) {
44+ Collections .sort (Arrays .asList (intervals ), (o1 ,o2 ) -> {
4445if (o1 .end !=o2 .end ) {
4546return o1 .end -o2 .end ;
4647 }else {
4748return o2 .start -o1 .start ;
4849 }
50+ });
51+ int end =Integer .MIN_VALUE ;
52+ int count =0 ;
53+ for (Interval interval :intervals ) {
54+ if (interval .start >=end ) {
55+ end =interval .end ;
56+ }else {
57+ count ++;
58+ }
4959 }
50- });
51- int end =Integer .MIN_VALUE ;
52- int count =0 ;
53- for (Interval interval :intervals ) {
54- if (interval .start >=end ) {
55- end =interval .end ;
56- }else {
57- count ++;
58- }
60+ return count ;
5961 }
60- return count ;
61- }
62-
63- public static void main (String ...args ) {
64- //[[1,100],[11,22],[1,11],[2,12]]
65- Interval interval1 =new Interval (1 ,100 );
66- Interval interval2 =new Interval (11 ,22 );
67- Interval interval3 =new Interval (1 ,11 );
68- Interval interval4 =new Interval (2 ,12 );
69- Interval []intervals =new Interval []{interval1 ,interval2 ,interval3 ,interval4 };
70- System .out .println (eraseOverlapIntervals (intervals ));
7162 }
7263
73- }
64+ }