不得不说,这个算法还是不错的,就是Collections.sort()方法不会用。。。
新博文地址:[leetcode]Merge Intervals
Merge Intervals
Given a collection of intervals, merge all overlapping intervals.
For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].
For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].
这道题很容易,个人感觉比Insert Interval 还容易,题意就不多啰嗦了,直接说下算法吧:
首先按照start递增排序,然后逐个插入处理,本来懒得动脑,用的类似于比较排序的方式找list中最小的interval,时间复杂度为O(n*n),毫不意外的超时了,因此第二次用了类似于计数排序方式,时间复杂度,空间复杂度都为O(n)。
这里有个坑[1,2],[2,3]在Insert Interval 中是不合并的,但是在这道题中是合并的,不过对难度无影响
public List<Interval> merge(List<Interval> intervals) { List<Interval> list = new ArrayList<Interval>(); if (intervals == null || intervals.size() == 0) { return list; } int min = Integer.MAX_VALUE; int max = Integer.MIN_VALUE; Map<Integer, List<Interval>> map = new HashMap<Integer, List<Interval>>(); for (Interval inter : intervals) { min = inter.start < min ? inter.start : min; max = inter.start > max ? inter.start : max; if (map.containsKey(inter.start)) { map.get(inter.start).add(inter); } else { List<Interval> node = new ArrayList<Interval>(); node.add(inter); map.put(inter.start, node); } } intervals.clear(); for (int i = min; i <= max; i++) { if (map.containsKey(i)) { for (Interval in : map.get(i)) { intervals.add(in); } } } list.add(intervals.get(0)); for (int i = 1; i < intervals.size(); i++) { Interval last = list.get(list.size() - 1); if (last.end < intervals.get(i).start) { list.add(intervals.get(i)); } else { last.end = last.end > intervals.get(i).end ? last.end : intervals.get(i).end; } } return list; }
相关推荐
java java_leetcode题解之Merge Intervals.java
js js_leetcode题解之56-merge-intervals.js
c是最好的编程语言 C语言_leetcode题解之56-merge-intervals
例如,“Merge Intervals”(合并区间)要求我们合并时间重叠的事件区间,这需要用到排序和区间合并的技巧。"Valid Palindrome"(有效的回文串)则需要理解双指针法和忽略特定字符的策略。 最后的暗黑版《LeetCode ...
这是来自LeetCode的已解决任务的存储库使用Java语言解决任务 CoinChange.java - //leetcode....intervals/ ReverseLinkedList.java - //leetcode.com/problem
* Merge Intervals:该题目要求合并重叠的区间,实现方法使用了排序和迭代算法。 * Insert Interval:该题目要求将一个区间插入到另一个区间中,实现方法使用了排序和迭代算法。 三、字符串和动态规划 * String to...
# [LeetCode](https://leetcode.com/problemset/algorithms/) ![Language](https://img.shields.io/badge/language-Python%20%2F%20C++%2011-orange.svg) [![License]...
5. **Merge Intervals(using (Insert Interval) ).cpp** - 这是第56题“合并区间”的解冑,涉及到区间操作,尤其是如何有效地插入新区间并合并重叠区间。 6. **Integer to Roman.cpp** - 第40题,与“Roman to ...
【标题】"LeetCode56 - 合并间隔"是一个编程挑战,主要涉及算法和数据结构的知识点。在这个问题中,任务是合并一系列非重叠的整数区间,以形成尽可能少的连续区间。 【描述】LeetCode是全球知名的在线编程训练平台...
java lru leetcode :ice_cream: LeetCode Kindem 的个人 LeetCode 题解仓库,欢迎交流学习。 下面的目录中 $number 题号代表经典 LeetCode 题目,$number.$number ...LeetCode ...Merge Intervals 64 Minimum Path Sum 73
通常,LeetCode的问题解答会以问题的ID或题目名称来命名,例如 "001_two_sum.java" 或 "MergeIntervals.java"。这样的命名方式有助于用户快速识别代码对应的题目。 在解压并查看这些文件时,我们可以期待学习到以下...
leetcode 2 sum c LeetCode规划 LEETCODE PATTERNS 从LeetCode学演算法 Leetcode笔记 Leetcode 经典题目 程式题 1) reverse string Input: ["h","e","l","l","o"] Output: ["o","l","l","e","h"] 使用内部swap class...
9. Merge Intervals 区间合并是一个数组问题,要求合并重叠的区间。可以使用排序和迭代来解决该问题。 10. Insert Interval 区间插入是一个数组问题,要求将一个区间插入到已经排序的区间数组中。可以使用二分...
- Merge Intervals: 给定一组区间,请合并所有重叠的区间。 - Insert Interval: 在一组已经排序的区间中,插入一个新的区间。 - Rotate List: 给定一个链表的头节点head,当旋转了k个位置后,返回链表的新头节点。 -...
第56题,"Merge Intervals"(合并区间),是一道典型的区间处理问题,它考察了对排序、遍历以及区间合并的理解。在此,我们将深入探讨这个问题的解决方案,并结合C++编程技巧进行解析。 首先,我们要明确问题描述:...
def merge_intervals(intervals): # 1. 创建初始区间列表 intervals = [(start, start + 1) for start in intervals] # 2. 对区间进行排序 intervals.sort(key=lambda x: x[0]) # 3. 合并区间 merged_...
Intervals 进阶题目: Leetcode 179. Largest Number Leetcode 75. Sort Colors Leetcode 215. Kth Largest Element Leetcode 4. Median of Two Sorted Arrays 注意:后两题是与快速排序非常相似的快速选择(Quick ...
"Merge Intervals"(合并区间)则需要用到排序和区间合并的技巧。 二、算法篇 1. 回溯法:中等难度题目中,回溯法是一种常见的解决方案,如"Combination Sum"(组合总和)和"N-Queens"(皇后问题),通过回溯可以...
文件名可能按照LeetCode问题的ID或者题目名称来命名,例如“TwoSum.java”、“MergeIntervals.java”等,每个文件包含了解决特定问题的完整Java代码。 学习和分析这些代码可以帮助我们理解如何用Java高效地实现各种...