`
huntfor
  • 浏览: 201667 次
  • 性别: 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;
	}

 

 

分享到:
评论

相关推荐

    java-leetcode题解之Merge Intervals.java

    java java_leetcode题解之Merge Intervals.java

    js-leetcode题解之56-merge-intervals.js

    js js_leetcode题解之56-merge-intervals.js

    C语言-leetcode题解之56-merge-intervals.c

    c是最好的编程语言 C语言_leetcode题解之56-merge-intervals

    LeetCode 刷题笔记 with Java.zip

    例如,“Merge Intervals”(合并区间)要求我们合并时间重叠的事件区间,这需要用到排序和区间合并的技巧。"Valid Palindrome"(有效的回文串)则需要理解双指针法和忽略特定字符的策略。 最后的暗黑版《LeetCode ...

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

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

    LeetCode题解(java语言实现).pdf

    * Merge Intervals:该题目要求合并重叠的区间,实现方法使用了排序和迭代算法。 * Insert Interval:该题目要求将一个区间插入到另一个区间中,实现方法使用了排序和迭代算法。 三、字符串和动态规划 * String to...

    LeetCode最全代码

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

    Leetcode部分解答(126题)

    5. **Merge Intervals(using (Insert Interval) ).cpp** - 这是第56题“合并区间”的解冑,涉及到区间操作,尤其是如何有效地插入新区间并合并重叠区间。 6. **Integer to Roman.cpp** - 第40题,与“Roman to ...

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

    【标题】"LeetCode56 - 合并间隔"是一个编程挑战,主要涉及算法和数据结构的知识点。在这个问题中,任务是合并一系列非重叠的整数区间,以形成尽可能少的连续区间。 【描述】LeetCode是全球知名的在线编程训练平台...

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

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

    My leetcode.rar

    通常,LeetCode的问题解答会以问题的ID或题目名称来命名,例如 "001_two_sum.java" 或 "MergeIntervals.java"。这样的命名方式有助于用户快速识别代码对应的题目。 在解压并查看这些文件时,我们可以期待学习到以下...

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

    LeetCode题解 - Java语言实现-181页.pdf

    9. Merge Intervals 区间合并是一个数组问题,要求合并重叠的区间。可以使用排序和迭代来解决该问题。 10. Insert Interval 区间插入是一个数组问题,要求将一个区间插入到已经排序的区间数组中。可以使用二分...

    _leetcode-python.pdf

    - Merge Intervals: 给定一组区间,请合并所有重叠的区间。 - Insert Interval: 在一组已经排序的区间中,插入一个新的区间。 - Rotate List: 给定一个链表的头节点head,当旋转了k个位置后,返回链表的新头节点。 -...

    c++-c++编程基础之leetcode题解第56题合并区间.zip

    第56题,"Merge Intervals"(合并区间),是一道典型的区间处理问题,它考察了对排序、遍历以及区间合并的理解。在此,我们将深入探讨这个问题的解决方案,并结合C++编程技巧进行解析。 首先,我们要明确问题描述:...

    python入门-leetcode面试题解之第228题汇总区间.zip

    def merge_intervals(intervals): # 1. 创建初始区间列表 intervals = [(start, start + 1) for start in intervals] # 2. 对区间进行排序 intervals.sort(key=lambda x: x[0]) # 3. 合并区间 merged_...

    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刷题(中等难度分类)

    "Merge Intervals"(合并区间)则需要用到排序和区间合并的技巧。 二、算法篇 1. 回溯法:中等难度题目中,回溯法是一种常见的解决方案,如"Combination Sum"(组合总和)和"N-Queens"(皇后问题),通过回溯可以...

    leetcode

    文件名可能按照LeetCode问题的ID或者题目名称来命名,例如“TwoSum.java”、“MergeIntervals.java”等,每个文件包含了解决特定问题的完整Java代码。 学习和分析这些代码可以帮助我们理解如何用Java高效地实现各种...

Global site tag (gtag.js) - Google Analytics