题目地址
https://leetcode.com/problems/merge-intervals/description/
题目描述
Given a collection of intervals, merge all overlapping intervals.
Example 1:
Input: [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].
Example 2:
Input: [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.
NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.
思路
- 先对数组进行排序,排序的依据就是每一项的第一个元素的大小。
- 然后我们对数组进行遍历,遍历的时候两两运算(具体运算逻辑见下)
- 判断是否相交,如果不相交,则跳过
- 如果相交,则合并两项
关键点解析
- 对数组进行排序简化操作
- 如果不排序,需要借助一些hack,这里不介绍了
代码
- 语言支持: Javascript,Python3
/* * @lc app=leetcode id=56 lang=javascript * * [56] Merge Intervals */ /** * @param {number[][]} intervals * @return {number[][]} */ function intersected(a, b) { if (a[0] > b[1] || a[1] < b[0]) return false; return true; } function mergeTwo(a, b) { return [Math.min(a[0], b[0]), Math.max(a[1], b[1])]; } var merge = function(intervals) { // 这种算法需要先排序 intervals.sort((a, b) => a[0] - b[0]); for (let i = 0; i < intervals.length - 1; i++) { const cur = intervals[i]; const next = intervals[i + 1]; if (intersected(cur, next)) { intervals[i] = undefined; intervals[i + 1] = mergeTwo(cur, next); } } return intervals.filter(q => q); };
Python3 Code:
class Solution: def merge(self, intervals: List[List[int]]) -> List[List[int]]: """先排序,后合并""" if len(intervals) <= 1: return intervals # 排序 def get_first(a_list): return a_list[0] intervals.sort(key=get_first) # 合并 res = [intervals[0]] for i in range(1, len(intervals)): if intervals[i][0] <= res[-1][1]: res[-1] = [res[-1][0], max(res[-1][1], intervals[i][1])] else: res.append(intervals[i]) return resLeetCode题解计算机为什么是基于二进制的?
可以是三进制么?二进制有什么好处?题解:为什么叫电子计算机?算盘应该没有二进制
LeetCode题解深度优先遍历和回溯的关系?深度优先遍历的范围更大还是回溯的范围更大?为什么?题解:我的理解是:dfs是回溯思想的一种体现- 回溯:是在整个搜索空间中搜索出可行解,在搜索过程中不断剪枝回退,这是回溯的思想,这个搜索空间并没有限制于特定的数据结构。- dfs:dfs是指特定的数据结构中如图,树(特殊的图)中搜索答案,范围限制在了特定的数据结构。个人拙见。
LeetCode题解盲人买袜子。他们都各自买了两对黑袜和两对白袜,八对袜子的布质、大小完全相同,而每对袜子都有一张商标纸连着。两位盲人不小心将八对袜子混在一起。他们每人怎样才能取回黑袜和白袜各两对呢?题解:暴力破解, 把袜子都拆开 一人一只 哈哈
LeetCode题解白石搭白塔输入黑块和白块的数量,用输入的方块数目建塔,输出最大高度和种数,两种方法至少一层颜色不同才能算不同的方法塔满足下列要求:1. 塔底层块数和高度数值相同,逐层递减1,最高层为12. 每层颜色相同
LeetCode题解分鸡块外卖鸡块分别有 4,6,12 块, 每 固定块数不能分开装, 用户给一个数字, 要求返回满足用户订单(可以等于也可以大于)的最少的盒数的组合