`
huntfor
  • 浏览: 194193 次
  • 性别: Icon_minigender_1
  • 来自: 杭州
社区版块
存档分类
最新评论

[leetcode]Merge Intervals

 
阅读更多

不得不说,这个算法还是不错的,就是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].

 这道题很容易,个人感觉比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;
	}

 

 

分享到:
评论

相关推荐

    LeetCode最全代码

    # [LeetCode](https://leetcode.com/problemset/algorithms/) ![Language](https://img.shields.io/badge/language-Python%20%2F%20C++%2011-orange.svg) [![License]...

    LeetCodeTrain:这是来自LeetCode的已解决任务的存储库

    这是来自LeetCode的已解决任务的存储库使用Java语言解决任务 CoinChange.java - //leetcode....intervals/ ReverseLinkedList.java - //leetcode.com/problem

    leetcode56-Leetcode56---Merge-Intervals:Leetcode56---合并间隔

    leetcode56 Leetcode56 合并间隔

    javalruleetcode-LeetCode::lollipop:个人LeetCode习题解答仓库-多语言

    java lru leetcode :ice_cream: LeetCode Kindem 的个人 LeetCode 题解仓库,欢迎交流学习。 下面的目录中 $number 题号代表经典 LeetCode 题目,$number.$number ...LeetCode ...Merge Intervals 64 Minimum Path Sum 73

    leetcode2sumc-LeetCode:练习商务面试

    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...

    lrucacheleetcode-LeetCodeSheet:记录自己Leetcode之旅

    Intervals 进阶题目: Leetcode 179. Largest Number Leetcode 75. Sort Colors Leetcode 215. Kth Largest Element Leetcode 4. Median of Two Sorted Arrays 注意:后两题是与快速排序非常相似的快速选择(Quick ...

    leetcode分类-leetCode:leetcode

    leetcode 分类 ReadMe 纯粹记录一下自己leetCode做题记录及部分思路笔记,不充当指导性...intervals 区间合并类型 cyclic sort 循环排序 list 链表 ... 这些tag分类都可以在一些平台上找到,VSCode中也有响应的分类tag

    Coding Interview In Java

    11 Merge Intervals 43 12 Insert Interval 45 13 Two Sum 47 14 Two Sum II Input array is sorted 49 15 Two Sum III Data structure design 51 16 3Sum 53 17 4Sum 55 18 3Sum Closest 57 19 String to Integer ...

    gasstationleetcode-LeetCode:力码

    leetcode 力码 【吾生也有涯,而知也无涯。】 刷题解题记录: 大批: 220 包含重复 III 考 55 跳跃游戏45 跳跃游戏 II121 买卖股票的最佳时机 122 买卖股票的最佳时机 II123 买卖股票的最佳时机 III188 买卖股票的...

    LeetCode刷题笔记——56. 合并区间

    def merge(self, intervals: List[List[int]]) -&gt; List[List[int]]: intervals = sorted(intervals) # 区间从小到大排序,若左边界相等,则对右边界排序; i = 1 # 初始位置从第二个区间开始 while i = ...

    leetcode482-coding-test:编码测试

    MergeIntervals_56 [Java] Java LinkedList 用法和示例总结 MeetingRoomsII_253 [Java] PriorityQueue 类用法和示例总结 关于 KClosetPointsToOrigin_973 PriorityQueue(报告正确答案) FindAllAnagramsInAString_...

    leetcode2sumc-Fizz:嘶嘶声

    leetcode 2 和 c 嘶嘶声 C INT_MIN (-INT_MAX - 1) 力码 037 数独解算器 056 Merge Intervals:还没有检查连接组件方法 065 068 069 071 131 回文分区:动态规划 180 188个买卖股票的最佳时机IV:不懂最快的方法 218...

    Leetcode典型题解答和分析、归纳和汇总——T56(合并区间)

    vector&lt;vector&gt; merge(vector&lt;vector&gt;& intervals){ vector&lt;vector&gt; res; //作为返回结果 if(intervals.empty()) return res; sort(intervals.begin(),intervals.end()); //按照区间的左边界来进行排序 int ...

    leetcode中文版-LeetCode-OJ:我对leetcodeoj的回答

    leetcode中文版##LeetCode 在线裁判练习 更新频率:一天一题。 所有答案都是我自己完成的,换句话说,答案可能不是最好的,但可以接受。 从这些科目中,我发现动态规划非常重要。 ##难的 ###合并间隔 Given a ...

    猜单词leetcode-leetcodelearn:leetcodelearn

    猜单词leetcode leetcodelearn 2020-06-03 标题 2020-06-04 标题 2020-06-05 标题 2020-06-06 标题 2020-06-07 标题 标题 知识点 二分法 ...翻转单词顺序com/problems/merge-intervals/) 2020-06-20 标题

    cpp-算法精粹

    Merge Intervals Minimum Window Substring Multiply Strings Substring with Concatenation of All Words Pascal's Triangle Pascal's Triangle II Spiral Matrix Spiral Matrix II ZigZag Conversion Divide Two ...

Global site tag (gtag.js) - Google Analytics