合并区间__牛客网

页川先生

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)

Java

詆調壹點

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)

Python3

Vivimore

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)

nbgao

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)

Python3

云云云小雀

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)

C/C++

小目标，500题

//按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)

我寻思这打野走位就尼玛离谱儿

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)

C++

_ccc

插旗问题

时间复杂度：O(n)
空间复杂度：O(n)

class Solution {
public:
    vector<Interval> merge(vector<Interval> &intervals) {
        map <int, int> ss;
        for(auto &c : intervals) {
            ss[c.start]++;
            ss[c.end]--;
        }
        vector <Interval> ans;
        int cnt = 0, l;
        for(auto &[k, v] : ss) {
            if(!cnt) l = k;
            cnt += v;
            if(!cnt) ans.push_back(Interval(l, k));
        }
        return ans;
    }
};

发表于 2022-03-12 20:07:28 回复(0)

C++

include<cc>

题目说可以用O(val)的复杂度来做，我想到了差分数组，但是差分数组没办法区分相邻的两个为范围都是不0的情况，附上我的代码，有大神有缘看到了告诉我一下O(val)到底怎么做的:

/**
 * 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<int> diff(1002);
        for(auto &interval:intervals){
            diff[interval.start]++;
            diff[interval.end+1]--;
        }
        vector<Interval> res;
        int pre = -1,sum = 0;
        for(int i = 0;i < 1002;i++){
            int tem = sum;
            sum += diff[i];
            if(sum > 0 && tem == 0) pre = i;
            else if(sum == 0 && tem > 0){
                res.push_back(Interval(pre,i-1));
            }
        }
        
        return res;
    }
};

发表于 2021-10-21 09:14:10 回复(1)

Python

风海洋

和大部分人的代码不一样，没有定义两个类，思路却容易理解

class Solution:
    def merge(self , intervals ):
        intervals.sort()#按第一个数字排序以防输入的区间顺序错乱
        list1=[]
        while len(intervals)>1:#为了使后续语句intervals[1][0]不出现越界错误，故设置长度大于1
            if intervals[0][1]<intervals[1][0]:#前一个区间的上界小于后一个区间的下界，说明两个区间没有交集，直接添加
                list1.append(intervals[0])
                intervals.pop(0)#添加完成删除该区间
            else:#否则两个区间有交集
                intervals[0]=[min(intervals[0][0],intervals[1][0]),max(intervals[0][1],intervals[1][1])]#取两个区间的下界的最小值作为合并后区间的下界，取两个区间的上界的最大值作为合并后区间的上界，即完成两个区间的并集
                intervals.pop(1)#合并后intervals的第一个元素用合并后的区间替换，那么参与合并的第二个元素（下标为1）也应该要删除
        list1.append(intervals[0])#intervals还剩一个元素即退出循环体，故剩下的一个元素需要添加进来
        list1=map(str,list1)#将列表元素的数据类型由整型转化为字符串，才能使用下面的join语句，否则报错
        return ",".join(list1)#返回列表的所有元素，即去掉中括号后的列表
#print(Solution().merge([[18,18],[1,2],[8,10],[4,11],[0,8],[19,22]]))

发表于 2020-09-19 18:13:08 回复(1)

LinuX18

class Solution {
public:   
    // 先按照start从小到大时间轴排序，有重叠部分则进行合并
    static bool compare(const Interval &a,const Interval &b)
    {
       return (a.start < b.start); 
    }
    vector<Interval> merge(vector<Interval> &intervals)
    {
        vector<Interval> res;
        int len = intervals.size();
        if(len==0) return res;
        sort(intervals.begin(),intervals.end(),compare);
        res.push_back(intervals[0]);
        
        for(int i=1;i<len;i++)
        {
            if(res.back().end >= intervals[i].start)
                res.back().end = max(res.back().end,intervals[i].end);
            else
                res.push_back(intervals[i]);
        }
        return res;
    }
};

发表于 2017-07-08 15:53:53 回复(2)

C++

TokaiTeio_

/**
 * struct Interval {
 *	int start;
 *	int end;
 *	Interval(int s, int e) : start(start), end(e) {}
 * };
 */
#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param intervals Interval类vector 
     * @return Interval类vector
     */
    vector<Interval> merge(vector<Interval>& intervals) {
        // write code here
        vector<int>dpl(2e5 + 10,0);
        vector<int>dpr(2e5 + 10,0);
        vector<Interval>ans;
        Interval A;
        for(auto [l,r] : intervals)
        {
            dpl[l] += 1;
            dpr[r] += 1;
        }
        int sum = 0;
        int l;
        for(int i = 0; i <= 2e5; i ++ )
        {
            if(!sum && dpl[i]) l = i;
            sum += dpl[i] - dpr[i];
            if(!sum && dpr[i])
            {
                A.start = l;
                A.end = i;
                ans.push_back(A);
            }
        }
        return ans;
    }
};

发表于 2024-08-16 20:26:19 回复(0)

Java

五呀

写得很烦

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) {
        if (intervals.size() == 0) {
            return new ArrayList<>();
        }
        ArrayList<Interval> res = new ArrayList<>();
        res.add(intervals.get(0));
        for (int i = 1; i < intervals.size(); i++) {
            res = inside(intervals.get(i), res);
        }
        return res;
    }

    ArrayList<Interval> inside(Interval newinterval,
                               ArrayList<Interval> hasinside) {
        int i = 0;
        for (; i < hasinside.size(); i++) {
            Interval temp = hasinside.get(i);
            if (newinterval.start > temp.end) {
                continue;
            }
            if (newinterval.start >= temp.start) {
                goend(i, hasinside, temp, newinterval);
                break;
            } else {
                if (newinterval.end < temp.start) {
                    hasinside.add(i, newinterval);
                    return hasinside;
                }
                temp.start = newinterval.start;
                goend(i, hasinside, temp, newinterval);
                break;
            }
        }
        if(i==hasinside.size()){
            hasinside.add(newinterval);
        }
        return hasinside;
    }
    void goend(int i, ArrayList<Interval> hasinside, Interval temp,
               Interval newinterval) {
        int j = i;
        for (; j < hasinside.size(); j++) {
            if (hasinside.get(j).end > newinterval.end) {
                break;
            }
        }
        if (j < hasinside.size()) {
            if (newinterval.end < hasinside.get(j).start) {
                temp.end = newinterval.end;
                j--;
            } else {
                temp.end = hasinside.get(j).end;
            }
        } else {
            temp.end = newinterval.end;
            j--;
        }

        while (j > i) {
            hasinside.remove(j);
            j--;
        }
    }
}

发表于 2022-11-18 22:32:48 回复(0)

Java

Friedrich123

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<>();
        if(intervals.size()==0) return res;
        // 排序
        intervals.sort((a,b)->a.start-b.start);

        // 放入首值
        res.add(intervals.get(0));
        // 用于取索引
        int count = 0;

        for(int i=1;i<intervals.size();i++){
            Interval curr = intervals.get(i);
            Interval tmp = res.get(count);

            if(curr.start<=tmp.end) 
            // 更新end值
                tmp.end = Math.max(tmp.end, curr.end);
            else {
                res.add(curr);
                count++;
            }
        }
        return res;
    }
}

发表于 2022-11-17 14:50:20 回复(1)

c++好难

/**
 * 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)

llch__

    Comparator<Interval> cmp = new Comparator<Interval>() {
        @Override
        public int compare(Interval o1, Interval o2) {
            // TODO Auto-generated method stub
            if(o1.start > o2.start) return 1;
            else return -1;            
        }
    };
    public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
        if(intervals.size()<= 1) return intervals;
        ArrayList<Interval> result = new ArrayList<Interval>();
        intervals.sort(cmp);
        int start = intervals.get(0).start;
        int end = intervals.get(0).end;
        for(int i=1; i<intervals.size(); i++){
            Interval interval = intervals.get(i);
            if(interval.start>end){
                result.add(new Interval(start,end));
                start = interval.start;
                end = interval.end;
                continue;
            }
            if(interval.start <= start && start<=interval.end) start = interval.start;
            if(interval.start <= end   && end <= interval.end) end = interval.end;
        }
        result.add(new Interval(start, end));
        return result;
    }

发表于 2018-07-28 11:40:12 回复(0)

Wg_yh

//merge intervals
/* 思路：先对intervals进行排序，然后对intervals进行两两对比 

class Solution
{
public:
    static bool compare(const Interval &a,const Interval &b)    //仅本作用域可见
    {
        return (a.start<b.start);
    }

    vector<Interval> merge(vector<Interval> &intervals)
    {
        vector<Interval> res;
        if(intervals.empty())   return res;
        sort(intervals.begin(),intervals.end(),compare);
        res.push_back(intervals[0]);
        
        //已经排好序了，只需要进行两两的比较即可
        for(int i=1;i<intervals.size();++i)
        {
            if(res.back().end>=intervals[i].start)
            {
                res.back().end=max(res.back().end,intervals[i].end);
            }
            else
            {
                res.push_back(intervals[i]);
            }
        }

        return res;

    }
};

发表于 2017-04-11 09:58:45 回复(3)

xiao_lai

#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)

合并区间

输入

输出

输入

输出

插旗问题

问题信息

热门推荐

通过挑战的用户

相关试题