合并区间

傷城~ 2022-01-22 00:53 290阅读 0赞

## 题目描述 ##

给出一个区间的集合，请合并所有重叠的区间。

示例 1:

输入: [[1,3],[2,6],[8,10],[15,18]]
    输出: [[1,6],[8,10],[15,18]]
    解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2:

输入: [[1,4],[4,5]]
    输出: [[1,5]]
    解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。

## 解题 ##

#### 思路 ####

![在这里插入图片描述][20190604172317212.png_x-oss-type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9ob25nX2Jv_size_16_color_FFFFFF_t_70]

#### 代码实现 ####

public int[][] merge(int[][] intervals) { 
    		List<int[]> list = new ArrayList<int[]>();
    		
    		for(int[] arr:intervals) { 
    			list.add(arr);
    		}
    		//先按照集合左端进行排序
            Collections.sort(list, new Comparator<int[]>() { 
    
    			public int compare(int[] o1, int[] o2) { 
    				return o1[0]-o2[0];
    			}
    		});
            
            List<int[]> res = new ArrayList<int[]>();
            int maxIndex =0;
            for(int[] arr:list) { 
            	maxIndex = res.size()-1;
            	if(res.isEmpty() || res.get(maxIndex)[1]<arr[0]) { 
            		res.add(arr);
            	}else { 
            		res.get(maxIndex)[1] = Math.max(res.get(maxIndex)[1], arr[1]);
    			}
            }
            return res.toArray(new int[res.size()][2]);
        }

[20190604172317212.png_x-oss-type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9ob25nX2Jv_size_16_color_FFFFFF_t_70]: /images/20220122/caf4a2759b2946e290bddd85d345dd75.png

发表评论取消回复

表情：

评论列表（有 0 条评论，290人围观）

还没有评论，来说两句吧...

相关阅读

相关 56. 合并区间

56. 合并区间题干描述解题思路代码实现题干描述 [力扣入口][Link 1] 给出一个区间的集合，请合并所有重叠的区间。示例 1

朴灿烈づ我的快乐病毒、/ 2023年10月16日 15:42/ 0 赞/ 147 阅读

相关 56. 合并区间

打卡!!!每日一题今天这道题难度一般，主要是感觉挺好玩的，和大家分享一下。题目描述：[56. 合并区间][56.] > 以数组 intervals 表示若干个区间的集

拼搏现实的明天。/ 2023年10月11日 19:38/ 0 赞/ 82 阅读

相关 803. 区间合并

给定 n 个区间 \[li,ri\]，要求合并所有有交集的区间。注意如果在端点处相交，也算有交集。输出合并完成后的区间个数。例如：\[1,3\] 和 \[2,6\]

曾经终败给现在/ 2023年09月29日 13:55/ 0 赞/ 14 阅读

相关区间合并 AcWing 803. 区间合并

区间合并 AcWing 803. 区间合并原题链接 [AcWing 803. 区间合并][AcWing 803.] 算法标签区间合并贪心思路

古城微笑少年丶/ 2023年09月28日 11:32/ 0 赞/ 126 阅读

相关 56合并区间

一、前言标签：排序合并。问题来源LeetCode 56 难度：中等。问题链接：[https://leetcode-cn.com/problems/merge-i

布满荆棘的人生/ 2023年03月01日 09:15/ 0 赞/ 18 阅读

相关区间合并算法

算法:st,ed表示当前区间的左端点和右端点 1.将所有区间按左端点排序 2.扫描整个区间,扫描的过程中,将所有可能有交集的区间合并 (1)a区间在当前区间的内部:st和

港控/mmm°/ 2022年10月27日 01:40/ 0 赞/ 151 阅读

相关 56. 合并区间

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals\[i\] = \[starti, endi\] 。请你合并所有重叠的区间，并返回一个不重叠

快来打我*/ 2022年08月31日 07:19/ 0 赞/ 226 阅读

相关【leetcode】合并区间

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

超、凢脫俗/ 2022年03月08日 09:54/ 0 赞/ 286 阅读

相关合并区间

题目描述给出一个区间的集合，请合并所有重叠的区间。示例 1: 输入: [[1,3],[2,6],[8,10],[15,18]] 输出: [[1,6

傷城~/ 2022年01月22日 00:53/ 0 赞/ 291 阅读

相关 LeetCode：合并区间

给出一个区间的集合，请合并所有重叠的区间。 > 来源：力扣（LeetCode）链接：[https://leetcode-cn.com/problems/merge-inte

梦里梦外;/ 2021年11月16日 14:24/ 0 赞/ 345 阅读