首页 > 试题广场 >

合并区间

[编程题]合并区间
  • 热度指数:151368 时间限制:C/C++ 2秒,其他语言4秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
给出一组区间,请合并所有重叠的区间。
请保证合并后的区间按区间起点升序排列。

数据范围:区间组数 ,区间内 的值都满足
要求:空间复杂度 ,时间复杂度
进阶:空间复杂度 ,时间复杂度
示例1

输入

[[10,30],[20,60],[80,100],[150,180]]

输出

[[10,60],[80,100],[150,180]]
示例2

输入

[[0,10],[10,20]]

输出

[[0,20]]
import java.util.*;
/**
 * 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 ArrayList<Interval> merge(ArrayList<Interval> intervals) {
        // 排序后再处理,更方便,后续只要关注 end1 和 [start2,end2] 的关系就行
        Collections.sort(intervals,(o1,o2)->{
            if(o1.start != o2.start){
                return o1.start-o2.start;
            }else{
                return o1.end-o2.end;
            }
        });
        for(int i=0;i<intervals.size()-1;i++){
            // end1 >= end2,说明第二个区间都包裹在第一个区间里,直接移除掉第二个区间
            if(intervals.get(i).end >= intervals.get(i+1).end){
                intervals.remove(i+1);
                i--;
            }
            // end2 > end1 >= star2,说明这两个区间可以首尾合并,end1 = end2,直接移除第二个区间
            else if(intervals.get(i).end >= intervals.get(i+1).start){
                intervals.get(i).end = intervals.get(i+1).end;
                intervals.remove(i+1);
                i--;
            }
            // 其他情况都不需要处理
        }
        return intervals;
    }
}

发表于 2022-04-20 22:37:40 回复(0)
/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
class Solution {
public:
  vector<Interval> merge(vector<Interval> &intervals) {
    vector<Interval> ans;
    sort(begin(intervals), end(intervals), [](const auto& a, const auto& b) {
      return a.start < b.start;
    });
    for (const auto& interval : intervals) {
      if (ans.empty() || interval.start > ans.back().end)
        ans.emplace_back(interval);
      else
        ans.back().end = max(ans.back().end, interval.end);
    }
    return ans;
  }
};

发表于 2021-07-08 17:04:44 回复(0)
import java.util.*;
/**
 * 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 ArrayList<Interval> merge(ArrayList<Interval> intervals) {
        ArrayList<Interval> res = new ArrayList<>();
        Collections.sort(intervals, new Comparator<Interval>() {
            public int compare(Interval a, Interval b) {
                return a.start - b.start;
            }
        });
        int i = 0;
        while(i < intervals.size()) {
            int left = intervals.get(i).start;
            int right = intervals.get(i).end;
            while(i < intervals.size()-1 && right >= intervals.get(i+1).start){
                right = Math.max(right,intervals.get(i+1).end);
                i++;
            }
            res.add(new Interval(left, right));
            i++;
        }
        return res;
        
    }
}

发表于 2021-06-10 16:52:27 回复(0)
正常实现就行了啊 先排个序
然后判断当前interval的start是否小于res中的最后一个的end 
小于的话再判断end是否小于,若小于则continue
大于则res.reomve最后一个,再add当前
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

public class Solution {
    public ArrayList<Interval> merge(ArrayList<Interval> intervals) {

        ArrayList<Interval> res = new ArrayList<>();

        if (intervals.size() == 0) {
            return res;
        }
        Collections.sort(intervals);
        res.add(intervals.get(0));

        for (int i = 1; i < intervals.size(); i++) {
            Interval tmp = intervals.get(i);
            Interval pre = res.get(res.size() - 1);
            if (tmp.start <= pre.end) {
                if (tmp.end <= pre.end) {
                    continue;
                } else {
                    res.remove(res.size() - 1);
                    res.add(new Interval(pre.start, tmp.end));
                }

            } else {
                res.add(tmp);
            }


        }
        return res;
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        ArrayList<Interval> intervals = new ArrayList<>();
//        intervals.add(new Interval(10, 30));
//        intervals.add(new Interval(20, 60));
//        intervals.add(new Interval(80, 100));
//        intervals.add(new Interval(150, 180));
        intervals.add(new Interval(1,4));
        intervals.add(new Interval(0,4));

        s.merge(intervals);
    }

}

class Interval implements Comparable<Interval> {
    int start;
    int end;

    Interval() {
        start = 0;
        end = 0;
    }

    Interval(int s, int e) {
        start = s;
        end = e;
    }

    @Override
    public int compareTo(Interval o) {
        if (this.start == o.start) {
            return this.end > o.end ? 1 : -1;
        }
        return (this.start > o.start) ? 1 : -1;
    }
}

发表于 2021-03-26 06:19:20 回复(0)
/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
class Solution {
public:
    vector<Interval> merge(vector<Interval> &intervals) {
        if(intervals.size() <= 1)
            return intervals;
        vector<Interval> vec;
        sort(intervals.begin(),intervals.end(),[](Interval a,Interval b){return a.start < b.start;});
        Interval tmp = intervals[0];
        for(int i = 1; i < intervals.size(); ++i)
        {
            if(tmp.end < intervals[i].start)
            {
                vec.push_back(tmp);
                tmp = intervals[i];
            }
            else
                tmp.end = max(intervals[i].end,tmp.end);
        }
        vec.push_back(tmp);
        return vec;
    }
};

发表于 2019-12-19 15:03:53 回复(0)

思路

1.先将Interval数组按照start、end从小到大进行排序;
2.设置指针i,从头遍历到intervals.size() - 1,当intervals.get(i).end >= intervals.get(i).start时候,将这两个元素进行合并,然后更新最大的end,以便接下来继续遍历比较;
3.如果结束循环的时候,i == intervals.size() - 1,那么需要将intervals.get(i)加入到结果集合中。

import java.util.ArrayList;
import java.util.Collections;

/**
 * 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 ArrayList<Interval> merge(ArrayList<Interval> intervals) {
        ArrayList<Interval> res = new ArrayList<>();
        Collections.sort(intervals, (o1, o2) -> o1.start != o2.start ? o1.start - o2.start : o1.end - o2.end);
        int i = 0;
        while (i < intervals.size() - 1) {
            int left = intervals.get(i).start;
            int right = intervals.get(i).end;
            while (i < intervals.size() - 1 && intervals.get(i + 1).start <= right) {
                right = Math.max(right, intervals.get(i + 1).end);
                i++;
            }
            res.add(new Interval(left, right));
            i++;
        }
        if (i == intervals.size() - 1) {
            res.add(intervals.get(i));
        }
        return res;
    }
}
发表于 2019-11-04 17:16:05 回复(1)
/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
class Solution {
public:
    vector<Interval> merge(vector<Interval> &intervals) {
        int s=intervals.size();
        if(s==0) return intervals;
        for(int i=0;i<s;++i){
            int m=intervals[i].start;
            int tmp=i;
            for(int j=i;j<s;++j){
                if(intervals[j].start<m){
                    m=intervals[j].start;
                    tmp=j;
                }
            }
            int temp=intervals[i].start;
            intervals[i].start=intervals[tmp].start;
            intervals[tmp].start=temp;
            temp=intervals[i].end;
            intervals[i].end=intervals[tmp].end;
            intervals[tmp].end=temp;
        }
        for(int i=0;i<intervals.size()-1;++i){
            if(intervals[i].start==intervals[i+1].start){
                intervals.erase(intervals.begin()+(intervals[i].end>intervals[i+1].end?i+1:i));
                --i;
            }
            else if(intervals[i].end>=intervals[i+1].start){
                intervals[i].end=(intervals[i].end>intervals[i+1].end?intervals[i].end:intervals[i+1].end);
                intervals.erase(intervals.begin()+i+1);
                --i;
            }
        }
        return intervals;
    }
};

发表于 2018-08-09 15:37:47 回复(0)
/**
 * 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; }
 * }
 */
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;

public class Solution {
    public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
        if(intervals==null || intervals.size()<=1){
    		return intervals;
    	}
    	//对链表的start进行升序排序
    	Comparator<Interval> comparator = new Comparator<Interval>(){
    		public int compare(Interval s1,Interval s2){
    			return s1.start-s2.start;
    		}
    	};
    	Collections.sort(intervals,comparator);
    	//
    	for(int i=1;i<intervals.size();i++){
    	
    		if(intervals.get(i).start>intervals.get(i-1).end){
    		
    		}else{
    			
    			int maxEnd = Math.max(intervals.get(i-1).end, intervals.get(i).end);
    			Interval temp = new Interval(intervals.get(i-1).start,maxEnd);
    			intervals.set(i-1, temp);
    			intervals.remove(i);
    			i--;
    			
    		}
    	}
		return intervals;
    }
}

发表于 2016-03-17 17:08:49 回复(0)
#include<math.h>
bool comp(const Interval &in1,const Interval &in2){
    if(in1.start==in2.start){
        return in1.end<in2.end;
    }else{
        return in1.start<in2.start;
    }
}
class Solution {
public:
    vector<Interval> merge(vector<Interval> &intervals) {
        sort(intervals.begin(),intervals.end(),comp); //按start升序排序
        vector<Interval> res;
        int len = intervals.size();
        for(int i=0;i<len;i++){
            if(res.empty()){
                res.push_back(intervals[i]);
            }else{
                Interval last = res.back();
                if(last.end>=intervals[i].start){ //需要进行合并
                    res.pop_back();
                    last.end = max(last.end,intervals[i].end);
                    res.push_back(last);
                }else{
                    res.push_back(intervals[i]);
                }
            }
        }
        return res;
    }
};

编辑于 2016-06-25 19:13:46 回复(0)
function merge( $intervals)
{
    // write code here
    $total_intervals = count($intervals);
    $new_intervals = [];
    print_r($new_intervals);
    for($i = 0; $i < $total_intervals; $i++){
        $start = $intervals[$i]->start;
        $end = $intervals[$i]->end;
        for ($j = $i+1; $j < $total_intervals; $j++){
            if($end > $intervals[$j]->start){
                $end = $intervals[$j]->end;
                continue;
            }
            break;
        }
        
        array_push($new_intervals, [$start, $end]);
        $i = $j-1;
    }
    return $new_intervals;
}
发表于 2021-09-26 14:46:53 回复(0)
/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
/*
思路:
注意先对数组进行排序
*/
class Solution {
public:
    vector<Interval> merge(vector<Interval>& intervals) {
        vector<Interval> v;
        int n = intervals.size();

        if (0 == n) {
            return v;
        }
        if (1 == n) {
            v.push_back(intervals[0]);
            return v;
        }

        sort(intervals.begin(),intervals.end(),  compare_Interval); 

        Interval temp = intervals[0];
        int i = 1;

        while (i < n) {
            if (temp.end < intervals[i].start) {
                v.push_back(temp);
                temp = intervals[i];
                ++i;
                if (i == n) {
                    v.push_back(temp);
                }
            }
            else {
                temp.start = min(temp.start, intervals[i].start);
                temp.end = max(temp.end, intervals[i].end);
                ++i;

                if (i == n) {
                    v.push_back(temp);
                }
            }
        }

        return v;
    }

    static int compare_Interval(Interval val1, Interval val2){  
        return val1.start < val2.start;  
    }
};
编辑于 2017-11-29 22:15:05 回复(0)
static bool comp(const Interval& a,const Interval& b){
        return (a.start<= b.start);
    }
    
    vector<Interval> merge(vector<Interval> &intervals) {
        if(intervals.size()==0)
            return intervals;
        sort(intervals.begin(),intervals.end(),comp);
        vector<Interval> res;
        res.push_back(intervals[0]);
        for(int i=1;i<intervals.size();i++){
            if(intervals[i].start>res.back().end)
                res.push_back(intervals[i]);
            else{
                res.back().end=std::max(intervals[i].end,res.back().end);
            }
        }
        return res;
    }

发表于 2017-11-06 15:53:36 回复(0)
import java.util.*;
public class Solution {
    public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
		if(intervals.size() < 2) return intervals;
		Collections.sort(intervals, new Comparator<Interval>() {
			@Override
			public int compare(Interval o1, Interval o2) {
				if(o1.start == o2.start) return o1.end < o2.end ? - 1 : 1;
				return o1.start < o2.start ? - 1 : 1;
			}
		});
		ArrayList<Interval> list = new ArrayList<>();
		list.add(intervals.get(0));
		for (int i = 1; i < intervals.size(); i ++) {
			Interval cur = intervals.get(i);
			Interval ready = list.get(list.size() - 1);
			if(cur.start <= ready.end) {
				ready.end = cur.end > ready.end ? cur.end : ready.end;
				list.remove(list.size() - 1);
				list.add(ready);
			} else list.add(cur);
		}
		return list;
	}
}

发表于 2017-03-25 16:25:38 回复(0)
// 想法很简单,先排个序,按照start的升序,然后依次和后面的interval比较有没有交集
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
public class Solution {
    public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
        ArrayList<Interval> list = new ArrayList<>();
		if(intervals == null)
			return list;
		if(intervals.size() <= 1)
			return intervals;
		Collections.sort(intervals, new Comparator<Interval>() {
			public int compare(Interval int1, Interval int2){
				return int1.start - int2.start;
			}
		});
		
		Interval cur = intervals.get(0);
		for(int i = 1; i < intervals.size(); i++){
			if(cur.end >= intervals.get(i).start){
				cur.start = Math.min(cur.start, intervals.get(i).start);
				cur.end = Math.max(cur.end, intervals.get(i).end);
				if(i == intervals.size() - 1)
					list.add(cur);
			}
			else{
				list.add(cur);
				cur = intervals.get(i);
				if(i == intervals.size() - 1)
					list.add(cur);
			}
		}
		return list;
    }
}

发表于 2017-05-15 14:51:03 回复(0)
import java.util.*;
public class Solution {
    public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
        Collections.sort(intervals, new Comparator<Interval>() {
            public int compare(Interval o1, Interval o2) {
                return o1.start-o2.start;
            }
        });
        for (int i = 1; i < intervals.size(); i++) {
            int preStart = intervals.get(i - 1).start;
            int preEnd = intervals.get(i - 1).end;
            int curStart = intervals.get(i).start;
            int curEnd = intervals.get(i).end;
            if (curStart <= preEnd) {
                intervals.set(i, new Interval(preStart, Math.max(preEnd, curEnd)));
                intervals.set(i - 1, null);
            }
        }

        while (intervals.remove(null)) ;
        return intervals;
    }
}

发表于 2017-11-22 18:47:42 回复(3)
class Solution {
public:
    vector<Interval> merge(vector<Interval> &intervals) {
        vector<Interval> result;
        int l = intervals.size();
        if(l==0)
            return result;
        sort(intervals.begin(), intervals.end(), cmp);
        result.push_back(intervals[0]);
        
        for(int i=1;i<l;i++)
        {
            if(result.back().end >= intervals[i].start)
                result.back().end = max(result.back().end, intervals[i].end);
            else
                result.push_back(intervals[i]);         }         return result;
    }
    static bool cmp(const Interval &a, const Interval &b)
    {
        return a.start < b.start;     }
};

发表于 2017-09-27 07:47:43 回复(2)
class Solution:
    def merge(self , intervals: List[Interval]) -> List[Interval]:
        if not intervals:
            return []
        intervals.sort(key=lambda x: x.start)
        res = [intervals[0]]
        for i in intervals[1:]:
            if res[-1].end < i.start:
                res.append(i)
            elif res[-1].end < i.end:
                res[-1].end = i.end
        return res
发表于 2022-05-26 20:59:39 回复(0)
class Solution:
    
    def merge(self , intervals ):
        # write code here
        
        intervals.sort(key=(lambda elme:elme.start))
        res = []
        for i in range (len(intervals)):
            if res == []:
                res.append(intervals[i])
            else:
                if res[-1].end >= intervals[i].start :
                    res[-1].end = max(intervals[i].end, res[-1].end)
                else:
                    res.append(intervals[i])
        return res

发表于 2021-09-02 00:31:11 回复(0)
import java.util.*;
public class Solution {
    public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
        ArrayList<Interval> res=new ArrayList<Interval>();
        if(intervals.size()==0||intervals==null)
            return res;
        Collections.sort(intervals, (a,b) -> a.start - b.start);
        for(int i=1;i<intervals.size();i++)
        {
            if(intervals.get(i).start<=intervals.get(i-1).end)
            {
                intervals.get(i).start=intervals.get(i-1).start;
                intervals.get(i).end=Math.max(intervals.get(i).end,intervals.get(i-1).end);
            }
            else
                res.add(intervals.get(i-1));
        }
        res.add(intervals.get(intervals.size()-1));
        return res;
    }
}

编辑于 2020-01-23 19:21:24 回复(0)
//按start进行排序,然后一个个的加到结果res中。
//如果待加入节点的start <= res.back().end 说明相交,直接更新end,取节点end和当res.back().end中的较大值。
//如果start > res.back()则不相交 直接加入res中。
//第一个节点,也直接加入res中
vector<Interval> merge(vector<Interval> &intervals) 
{
    sort(intervals.begin(), intervals.end(),[](Interval x, Interval y){return x.start < y.start;});

    vector<Interval> res;
    for (int i = 0; i < (int)intervals.size(); i++)
    {
        if (i == 0 || intervals[i].start > res.back().end)
        {
            res.push_back(intervals[i]);
        }
        else
        {
            res.back().end = max(intervals[i].end, res.back().end);
        }

    }
    return res;
}

发表于 2019-08-20 11:11:53 回复(0)