【LeetCode Top 100】56. Merge Intervals【Medium】【JAVA】

缺乏、安全感 2021-09-21 04:26 200阅读 0赞

## 1. 题目 ##

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

## 2. 题意 ##

题目很好理解，就是输入多个时间碎片，现在需要尽可能把碎片进行合并，求合并后的结果。

## 3. 思路 ##

一个比较容易想到的思路，`维护一个当前的合并之后的时间碎片组`，通过遍历所有的时间碎片，不断向合并之后的时间碎片组`加入新的时间碎片`，并将其进行`合并整理`即可。最佳的时间复杂度为O(n)，即每次加入的碎片都可以进行合并，维护的合并之后的时间碎片组永远只有一个碎片。最差的时间复杂度为O(n²)，即每次加入的碎片都无法进行合并，每次加入都只能与之前加入的所有碎片进行比较。

## 4. 解题代码 ##

public int[][] merge(int[][] intervals) { 
    		// 当输入为空，或碎片数不大于1时，可直接饭回
            if (intervals == null || intervals.length <= 1) { 
                return intervals;
            }
    
            // 加入第一块时间碎片
            List<int[]> lists = new ArrayList<>();
            lists.add(intervals[0]);
    
            // 遍历所有的时间碎片
            for (int i = 1; i < intervals.length; i++) { 
                int[] newInter = intervals[i];
                
                // 与维护的合并后的时间碎片组进行新一轮的合并
                for (int j = 0; j < lists.size(); j++) { 
                    int[] oldInter = lists.get(j);
                    
                    // 判断两个时间碎片是否有交集
                    if (overlap(oldInter, newInter)) { 
                    	// 有交集，即将原来的时间碎片与待放入的时间碎片进行合并
                        newInter[0] = Math.min(oldInter[0], newInter[0]);
                        newInter[1] = Math.max(oldInter[1], newInter[1]);
                        // 清除原来的时间碎片
                        lists.remove(j--);
                    }
                }
                // 将整合结果放入
                lists.add(newInter);
            }
    
            return lists.toArray(new int[lists.size()][]);
        }
    
        /** * 判断两个时间碎片是否有交集 */
        private boolean overlap(int[] oldInter, int[] newInter) { 
            return (oldInter[1] >= newInter[0] && newInter[1] >= oldInter[0]);
        }

## 5. 运行结果 ##

![在这里插入图片描述][20200314003504553.png]

## 6. 相关链接 ##

[本题代码的github链接][github]  
[其他 LeetCode 题目解析][LeetCode]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FwcGx5aW5n_size_16_color_FFFFFF_t_70]: /images/20210920/672877eb2a8047ff856d75cc6f39544a.png
[20200314003504553.png]: /images/20210920/1b847b42574347d289ee5438cdff06a8.png
[github]: https://github.com/Parallelline1996/Leetcode/blob/master/Problems/src/main/java/page1/N56_MergeIntervals.java
[LeetCode]: https://blog.csdn.net/applying/category_9629399.html