无重叠区间

怼烎@ 2024-04-06 13:13 17阅读 0赞

### 435. 无重叠区间 ###

> 给定一个区间的集合 intervals ，其中 intervals\[i\] = \[starti, endi\] 。返回 需要移除区间的最小数量，使剩余区间互不重叠 。

##### 示例 1: #####

> 输入: intervals = \[\[1,2\],\[2,3\],\[3,4\],\[1,3\]\]  
> 输出: 1  
> 解释: 移除 \[1,3\] 后，剩下的区间没有重叠。

##### 示例 2: #####

> 输入: intervals = \[ \[1,2\], \[1,2\], \[1,2\] \]  
> 输出: 2  
> 解释: 你需要移除两个 \[1,2\] 来使剩下的区间没有重叠。

##### 示例 3: #####

> 输入: intervals = \[ \[1,2\], \[2,3\] \]  
> 输出: 0  
> 解释: 你不需要移除任何区间，因为它们已经是无重叠的了。

##### 提示: #####

*   1 < = i n t e r v a l s . l e n g t h < = 1 0 5 1 <= intervals.length <= 10^5 1<=intervals.length<=105
 *   i n t e r v a l s \[ i \] . l e n g t h = = 2 intervals\[i\].length == 2 intervals\[i\].length==2
 *   − 5 ∗ 1 0 4 < = s t a r t i < e n d i < = 5 ∗ 1 0 4 -5 \* 10^4 <= starti < endi <= 5 \* 10^4 −5∗104<=starti<endi<=5∗104

##### 思路： #####

贪心算法：  
先计算最多能组成的不重叠区间个数，然后用区间总个数减去不重叠区间的个数。

在每次选择中，区间的结尾最为重要，选择的区间结尾越小，留给后面的区间的空间越大，那么后面能够选择的区间个数也就越大。

按区间的结尾进行排序，每次选择结尾最小，并且和前一个区间不重叠的区间。

##### 代码： #####

import java.util.Arrays;
    import java.util.Comparator;
    
    public class no_overlap {
        
    
    	public static void main(String[] args) {
        
    		
    		// TODO 自动生成的方法存根
    		int [][] intervals = {
         {
        1,2}, {
        1,2}, {
        1,2} };
    		int n = eraseOverlapIntervals(intervals);
    		System.out.println(n);
    	}
    	public static int eraseOverlapIntervals(int[][] intervals) {
        
    		if(intervals.length == 0)
    			return 0;
    		Arrays.sort(intervals, new Comparator<int[]>() {
        
    			public int compare(int[] interval1, int [] interval2) {
        
    				return interval1[1] - interval2[1];
    			}
    		});
    		
    		int n = intervals.length;
    		int cnt = 1;
    		int end = intervals[0][1];
    		
    		for(int i=1; i<n; i++) {
        
    			if(intervals[i][0] < end) {
        
    				continue;
    			}
    			end = intervals[i][1];
    			cnt++;
    		}
    		return intervals.length - cnt;
        }
    	
    	
    }

##### 复杂度分析 #####

*  时间复杂度：O(nlogn)，其中 n 是区间的数量。我们需要 O(nlogn) 的时间对所有的区间按照右端点进行升序排序，并且需要 O(n) 的时间进行遍历。由于前者在渐进意义下大于后者，因此总时间复杂度为 O(nlogn)。
 *  空间复杂度：O(logn)，即为排序需要使用的栈空间。

来源：[力扣（LeetCode）][LeetCode]

注：仅供学习参考。

[LeetCode]: https://leetcode.cn/problems/non-overlapping-intervals