找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 1311|回复: 3
收起左侧

[米群网刷题小分队] 【LeetCode小分队】【Merge Intervals】-【刷题第一弹】

[复制链接]

22

主题

6

精华

612

积分

超级会员

Rank: 4

积分
612
发表于 10-11-2014 11:20 PM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
本帖最后由 TeamEditor 于 11-19-2014 10:21 AM 编辑

Leetcode通道:https://oj.leetcode.com/problems/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].

思路:

关键是定义一个Comparator,然后对intervals数组排序, 合并相连的intervals。同时要利用排好序的数组/动态数组的特性。

代码:

1. O(n) time, O(n) space

  1. public class Solution {
  2.     public List<Interval> merge(ArrayList<Interval> intervals) {
  3.         if(intervals == null || intervals.size() <= 1) return intervals;
  4.       
  5.         Comparator<Interval> comparator = new Comparator<Interval>(){
  6.             public int compare(Interval i1, Interval i2){
  7.                return i1.start - i2.start;
  8.             }
  9.         };
  10.       
  11.         Collections.sort(intervals, comparator);
  12.       
  13.         ArrayList<Interval> result = new ArrayList<Interval>();
  14.       
  15.         Interval prev = intervals.get(0);
  16.         for(int i = 1; i < intervals.size(); ++i){
  17.             Interval curr = intervals.get(i);
  18.            
  19.             if(prev.end >= curr.start){
  20.                 Interval merged = new Interval(prev.start, Math.max(prev.end, curr.end));
  21.                 prev = merged;
  22.             } else {
  23.                 result.add(prev);
  24.                 prev = curr;
  25.             }
  26.         }
  27.         result.add(prev);
  28.         return result;
  29.     }
  30. }
复制代码

2. In-place处理, O(n) time, O(1) space

  1. public class Solution {
  2.     public List<Interval> merge(ArrayList<Interval> intervals) {
  3.         if(intervals == null || intervals.size() <= 1) return intervals;
  4.       
  5.         Comparator<Interval> comparator = new Comparator<Interval>(){
  6.             public int compare(Interval i1, Interval i2){
  7.                return i1.start - i2.start;
  8.             }
  9.         };
  10.       
  11.         Collections.sort(intervals, comparator);
  12.       
  13.         int cur = 0, next = 1;
  14.         while(next < intervals.size()){
  15.             if(intervals.get(cur).end >= intervals.get(next).start){
  16.                 intervals.get(cur).end = Math.max(intervals.get(cur).end, intervals.get(next).end);
  17.                 ++next;
  18.             } else {
  19.                 intervals.subList(cur+1, next).clear();
  20.                 ++cur;
  21.                 next = cur + 1;
  22.             }
  23.         }
  24.         if(cur < intervals.size() - 1){
  25.             intervals.subList(cur+1, intervals.size()).clear();
  26.         }
  27.         return intervals;
  28.     }
  29. }
复制代码


本帖被以下淘专辑推荐:

12

主题

5

精华

249

积分

高级会员

Rank: 3Rank: 3

积分
249

最佳新人

发表于 10-21-2014 06:16 PM | 显示全部楼层
思路:timeforce说的太好了!关键是排序,这里可以按照interval的start排序,排好序之后就非常容易进行merge了!对于排序之后的interval只有两种情况:
1. 后面的interval的start在第一个interval的end的后面,那就直接把后面的interval存入答案里
2. 后面的interval的start在第一个interval的end的前面,这时候只需要比较两个interval的end谁更大,取更大end作为merge后的end。这里的merge其实就是把之前的interval的end改成新的教大的end~

  1.     static bool compare(Interval a, Interval b) {
  2.         return a.start < b.start;
  3.     }

  4.     vector<Interval> merge(vector<Interval> &intervals) {
  5.         if(intervals.empty()) return intervals;
  6.         
  7.         vector<Interval> result;
  8.         int len = intervals.size();
  9.         
  10.         sort(intervals.begin(), intervals.end(), compare);
  11.         result.push_back(intervals[0]);
  12.         
  13.         for(int i = 1; i < intervals.size(); ++i) {
  14.             Interval &p = result.back();
  15.             if(intervals[i].start > p.end) result.push_back(intervals[i]);
  16.             else if(intervals[i].end > p.end) p.end = intervals[i].end;
  17.         }
  18.         
  19.         return result;
  20.     }
复制代码
回复 支持 反对

使用道具 举报

11

主题

10

精华

641

积分

超级会员

Rank: 4

积分
641
发表于 11-19-2014 01:45 AM | 显示全部楼层
我的代码和ls基本一样,为什么把compare从<改成<=就出现了runtime error呢?
  1.     vector<Interval> merge(vector<Interval> &intervals) {
  2.         sort(intervals.begin(), intervals.end(), comp);
  3.         
  4.         const int m = intervals.size();
  5.         vector<Interval> merged;
  6.         
  7.         if(m <= 0) return merged;
  8.         
  9.         merged.push_back(intervals[0]);

  10.         for(int i = 1; i < m; i++){
  11.             Interval &p = merged.back();
  12.             if(intervals[i].start > p.end){
  13.                 //Interval *tmp = new Interval(.start, intervals[i].end);
  14.                 merged.push_back(intervals[i]);
  15.             }
  16.             else if(p.end < intervals[i].end) p.end = intervals[i].end;
  17.         }

  18.         return merged;
  19.     }
  20.     static bool comp(const Interval &a, const Interval &b){
  21.         return a.start < b.start;
  22.     }
复制代码

补充内容 (11-19-2014 01:47 AM):
贴出来的代码通过了,[[74,78],[61,63],[46,50],[51,54],[50,50],[60,64],[39,42],[25,27],[91,95]...]这个用例错了
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表