[LeetCode] 435. Non-overlapping Intervals

轉自LeetCode

Given a collection of intervals, find the minimum number of intervals you need to remove to make the rest of the intervals 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.

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.

<Solution>

想法如下

• 這題和 452. Minimum Number of Arrows to Burst Balloons 可以用同思路來解

• 和 452 題不同點在於，本題是要找出，需要移掉多少個重疊的區間，才能讓所有區間都不重疊

• 一樣先找出不重疊區間有幾個，最後的答案，就會是 nums.length - cnt

code 如下

Java

	/**
	* Definition for an interval.
	* public class Interval {
	* int start;
	* int end;
	* Interval() { start = 0; end = 0; }
	* Interval(int s, int e) { start = s; end = e; }
	* }
	*/
	class Solution {
	public int eraseOverlapIntervals(Interval[] intervals) {
	if (intervals.length == 0) {
	return 0;
	}
	Arrays.sort(intervals, Comparator.comparingInt(o -> o.end));
	int cnt = 1;
	int end = intervals[0].end;
	for(int i = 1; i < intervals.length; i++) {
	if(intervals[i].start < end) {
	continue;
	}
	++cnt;
	end = intervals[i].end;
	}
	return intervals.length - cnt;
	}
	}

view raw eraseOverlapIntervals.java hosted with ❤ by GitHub

kotlin

	class Solution {
	fun eraseOverlapIntervals(intervals: Array<IntArray>): Int {
	intervals.sortBy{ it[1] }
	var nonOverlapCount = 1
	var end = intervals[0][1]
	for(i in 1..intervals.lastIndex) {
	if (intervals[i][0] < end) {
	continue
	}
	++nonOverlapCount
	end = Math.max(end, intervals[i][1])
	}
	return intervals.size - nonOverlapCount
	}
	}

view raw non_overlapping_intervals.kt hosted with ❤ by GitHub