- 浏览: 173918 次
- 性别:
- 来自: 济南
文章分类
最新评论
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].
题目中给定了一个interval集合,要求我们将集合中的interval合并,合并之后的interval是按照升序排列的。我们可以先将interval排序先按照interval的第一个元素,如果第一个元素相等就按照第二个元素。排序的时候我们定义一个比较器comparator。排序之后,从第二个interval开始,如果第二个interval的第一个元素等于或小于第一个interval的第二个元素,那么就将intervals[1].end = Math.max(intervals[2].end, intervals[1].end)。如果没有重叠,直接打入到结果集中。时间复杂度为O(nlogn)。代码如下:
For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].
题目中给定了一个interval集合,要求我们将集合中的interval合并,合并之后的interval是按照升序排列的。我们可以先将interval排序先按照interval的第一个元素,如果第一个元素相等就按照第二个元素。排序的时候我们定义一个比较器comparator。排序之后,从第二个interval开始,如果第二个interval的第一个元素等于或小于第一个interval的第二个元素,那么就将intervals[1].end = Math.max(intervals[2].end, intervals[1].end)。如果没有重叠,直接打入到结果集中。时间复杂度为O(nlogn)。代码如下:
/** * Definition for an interval. * public class Interval { * int start; * int end; * Interval() { start = 0; end = 0; } * Interval(int s, int e) { start = s; end = e; } * } */ public class Solution { public List<Interval> merge(List<Interval> intervals) { List<Interval> list = new ArrayList<Interval>(); if(intervals == null || intervals.size() == 0) return list; Collections.sort(intervals, new Comparator<Interval>() { @Override public int compare(Interval i1, Interval i2) { if(i1.start == i2.start) return i1.end - i2.end; return i1.start - i2.start; } }); list.add(intervals.get(0)); for(int i = 0; i < intervals.size(); i++) { if(list.get(list.size() - 1).end >= intervals.get(i).start) { list.get(list.size() - 1).end = Math.max(list.get(list.size() - 1).end, intervals.get(i).end); } else { list.add(intervals.get(i)); } } return list; } }
发表评论
-
498. Diagonal Traverse
2019-11-15 13:52 227Given a matrix of M x N eleme ... -
496 Next Greater Element I
2019-11-14 13:50 229You are given two arrays (witho ... -
Word Break II
2016-03-09 03:15 343Given a string s and a dictiona ... -
Insert Interval
2016-03-08 02:11 335Given a set of non-overlapping ... -
Merge k Sorted Lists
2016-03-07 04:03 514Merge k sorted linked lists and ... -
Multiply Strings
2016-03-06 07:27 431Given two numbers represented a ... -
N-Queens II
2016-03-06 03:06 622Follow up for N-Queens problem. ... -
N-Queens
2016-03-06 02:47 429The n-queens puzzle is the prob ... -
First Missing Positive
2016-03-05 03:09 388Given an unsorted integer array ... -
Spiral Matrix
2016-03-04 03:39 520Given a matrix of m x n element ... -
Trapping Rain Water
2016-03-04 02:54 534Given n non-negative integers r ... -
Repeated DNA Sequences
2016-03-03 03:10 371All DNA is composed of a series ... -
Increasing Triplet Subsequence
2016-03-02 02:48 862Given an unsorted array return ... -
Maximum Product of Word Lengths
2016-03-02 01:56 883Given a string array words, fin ... -
LRU Cache
2016-02-29 10:37 557Design and implement a data str ... -
Super Ugly Number
2016-02-29 07:07 602Write a program to find the nth ... -
Longest Increasing Path in a Matrix
2016-02-29 05:56 766Given an integer matrix, find t ... -
Coin Change
2016-02-29 04:39 737You are given coins of differen ... -
Minimum Height Trees
2016-02-29 04:11 631For a undirected graph with tre ... -
Bulb Switcher
2016-02-28 12:12 350There are n bulbs that are init ...
相关推荐
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 ...
这是来自LeetCode的已解决任务的存储库使用Java语言解决任务 CoinChange.java - //leetcode....intervals/ ReverseLinkedList.java - //leetcode.com/problem
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 ...
leetcode 2 sum c LeetCode规划 LEETCODE PATTERNS 从LeetCode学演算法 Leetcode笔记 ...intervals (第一类) ex: [1,2], [2,3], [4,5], [5,7] > [1,2,3], [4,5,7] 3) merge intervals (第二类) - M
...The number of questions is increasing recently. Here is the classification of all `468` questions. ...I'll keep updating for full summary and better solutions....|-----|---------------- | --------------- |...
java lru leetcode :ice_cream: LeetCode Kindem 的个人 LeetCode 题解仓库,欢迎交流学习。 下面的目录中 $number 题号代表经典 LeetCode 题目,$number.$number ...Merge Intervals 64 Minimum Path Sum 73
MergeIntervals_56 [Java] Java LinkedList 用法和示例总结 MeetingRoomsII_253 [Java] PriorityQueue 类用法和示例总结 关于 KClosetPointsToOrigin_973 PriorityQueue(报告正确答案) FindAllAnagramsInAString_...
Intervals 进阶题目: Leetcode 179. Largest Number Leetcode 75. Sort Colors Leetcode 215. Kth Largest Element Leetcode 4. Median of Two Sorted Arrays 注意:后两题是与快速排序非常相似的快速选择(Quick ...
│ │ ├── _056_MergeIntervals.java │ │ ├── _169_MajorityElement.java │ │ ├── _179_LargestNumber.java │ │ ├── _202_HappyNumber.java │ │ ├── _279_PerfectSquares.java │...
Intervals252Meeting Rooms253Meeting客房II352Data流从数据Stream53Maximum Subarray325Maximum大小子阵总和脱节IntervalsTreeMapCounter239Sliding窗口Maximum295Find中位数的距离和很少考289Game的提高321Create...
Intervals:还没有检查连接组件方法 065 068 069 071 131 回文分区:动态规划 180 188个买卖股票的最佳时机IV:不懂最快的方法 218 341 展平嵌套列表迭代器 371 两个整数的和 438 查找字符串中的所有字谜:哈希值 ...
检查任务模板这是用户生成任务的基本CheckiO模板。 它具有固定的文件夹结构,因此请谨慎使用文件和命名约定。任务示例一些例子几个用户创建了自己的任务,您可以在CheckiO上查看(并解决!)。 就像的。...
leetcode 分类 ReadMe 纯粹记录一下自己leetCode做题记录及部分思路笔记,不充当指导性...intervals 区间合并类型 cyclic sort 循环排序 list 链表 ... 这些tag分类都可以在一些平台上找到,VSCode中也有响应的分类tag
leetcode56 Leetcode56 合并间隔
def merge(self, intervals: List[List[int]]) -> List[List[int]]: intervals = sorted(intervals) # 区间从小到大排序,若左边界相等,则对右边界排序; i = 1 # 初始位置从第二个区间开始 while i = ...
vector<vector> merge(vector<vector>& intervals){ vector<vector> res; //作为返回结果 if(intervals.empty()) return res; sort(intervals.begin(),intervals.end()); //按照区间的左边界来进行排序 int ...
├───merge-intervals ├───miscellaneous ├───modified-binary-search ├───sliding-window ├───subsets ├───top-k-elements ├───topological-sort ├───tree-bfs ├───tree-dfs ├...
猜单词leetcode leetcodelearn 2020-06-03 标题 2020-06-04 标题 2020-06-05 标题 2020-06-06 标题 2020-06-07 标题 标题 知识点 二分法 ...翻转单词顺序com/problems/merge-intervals/) 2020-06-20 标题
merge all overlapping intervals. For example, Given [1,3],[2,6],[8,10],[15,18], return [1,6],[8,10],[15,18]. 首先,按开始对输入顺序进行排序。 其次,用游标将区间一一合并。 /** * Definition for an ...
features, Get started with data analysis tools in the pandas library, Use high-performance tools to load, clean, transform, merge, and reshape data, Create scatter plots and static or interactive ...