插入区间__牛客网

皮卡丘~

class Solution {
public:
    vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) {
        vector<Interval> res;
        int i=0;
        for(;i<intervals.size();i++){
            if(newInterval.end<intervals[i].start)
                break;
            else if(newInterval.start>intervals[i].end)
                res.push_back(intervals[i]);
            else{
                newInterval.start=min(newInterval.start,intervals[i].start);
                newInterval.end=max(newInterval.end,intervals[i].end);
            }
         
    }
        
        res.push_back(newInterval);
        for(;i<intervals.size();i++)
            res.push_back(intervals[i]);
    return res;
    }
};

发表于 2017-05-24 19:50:22 回复(1)

后劲好大

import java.util.ArrayList;
public class Solution {
    public ArrayList<Interval> insert(ArrayList<Interval> intervals, Interval newInterval) {
        ArrayList<Interval> result = new ArrayList<>();
		if(intervals == null || newInterval == null)
			return intervals;
		
		int insertInx = 0;
		for(Interval interval : intervals){
			if(interval.start > newInterval.end)
				result.add(interval);
			else if(interval.end < newInterval.start){
				result.add(interval);
                // 更新插入的位置
				insertInx++;
			}
			else{
                // 找到插入的公共区间
				newInterval.start = Math.min(interval.start, newInterval.start);
				newInterval.end = Math.max(interval.end, newInterval.end);
			}				
		}
		result.add(insertInx, newInterval);
		return result;
    }
}

编辑于 2017-05-23 19:39:27 回复(2)

JacobGo！

/*
	 * Runtime: 15 ms.Your runtime beats 77.22 % of java submissions.
	 */
	public ArrayList<Interval> insert(ArrayList<Interval> intervals, Interval newInterval) {
		//res存取最终结果
		ArrayList<Interval> res = new ArrayList<Interval>();
		int index = 0;
		//当intervals中interval区间与newInterval没有重叠时，直接添加到res集合中
		while (index < intervals.size() && newInterval.start > intervals.get(index).end)
			res.add(intervals.get(index++));
		//当存在重叠时，将newInterval赋予新的对象
		while (index < intervals.size() && newInterval.end >= intervals.get(index).start) {
			newInterval=new Interval(
					Math.min(newInterval.start, intervals.get(index).start),
					Math.max(newInterval.end, intervals.get(index).end));
			index++;
		}
		res.add(newInterval);
		//如果intervals中还有interval，直接添加到res中
		while (index < intervals.size())
			res.add(intervals.get(index++));
		
		return res;
	}

发表于 2017-06-27 10:41:53 回复(1)

C/C++

卷积神经网络哦

新数据扔进去一起排序时间复杂度O(nlgn)
然后从前往后依次合并
用栈就优雅的多如果区间没有重复就直接进栈
有重复就将栈顶元素和待合并元素的区间合并再进栈. 时间复杂度O(n)

static bool cmp(Interval a, Interval b){
    return a.start < b.start;
}

vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) {
    intervals.push_back(newInterval); 
    sort(intervals.begin(), intervals.end(), cmp);
    stack<Interval> sta; sta.push(intervals[0]);
    for(int i = 1; i < intervals.size(); i++){
        Interval &topI = sta.top();
        if(intervals[i].start > topI.end) sta.push(intervals[i]);
        else{
            topI.start = min(topI.start, intervals[i].start);
            topI.end = max(topI.end, intervals[i].end);
        }
    }
    vector<Interval> res;
    while(!sta.empty()){res.push_back(sta.top());sta.pop();}
    reverse(res.begin(), res.end());
    return res;
}

编辑于 2019-07-04 15:09:18 回复(0)

北坞一1

并归排序
/**
 * 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.*;
public class Solution {
    public static ArrayList<Interval> insert(ArrayList<Interval> intervals, Interval newInterval) {
        intervals.add(newInterval);
        ArrayList<Interval> re = merge(intervals,0,intervals.size()-1);
        return re;
    }
	private static ArrayList<Interval> merge(ArrayList<Interval> intervals, int start, int end) {
		ArrayList<Interval> result = new ArrayList<>();
		if(start>end) return result;
		if(start==end){
			result.add(intervals.get(start));
			return result;
		}
		ArrayList<Interval> left = merge(intervals,start,(start+end)/2);
		ArrayList<Interval> right = merge(intervals,(start+end)/2+1,end);
		int li=0;
		int ri=0;
		int rei=0;
		while(li<left.size()&&ri<right.size()){
			Interval l = left.get(li);
			Interval r = right.get(ri);
			Interval temp;
			if(l.start<r.start){temp = l;li++;}
			else {temp = r;ri++;}
			rei=add(rei,temp,result);
		}
		if(li<left.size()){
			for(int i=li;li<left.size();li++){
				rei=add(rei,left.get(li),result);
			}
		}else{
			for(int i=ri;ri<right.size();ri++){
				rei=add(rei,right.get(ri),result);
			}
		}
		return result;
	}
	private static int add(int rei, Interval temp, ArrayList<Interval> result) {
		for(int tmp = rei;tmp>=0;tmp--){
			if(tmp==0) {
				result.add(temp);
				rei=tmp+1;
				return rei;
			}
			Interval re = result.get(tmp-1);
			if(re.end>=temp.start){
				temp.start=re.start;
				temp.end = temp.end>re.end?temp.end:re.end;
				result.remove(tmp-1);
			}else{
				result.add(temp);
				rei=tmp+1;
				return rei;
			}
		}
		return 0;
	}
}

发表于 2017-06-12 18:45:06 回复(0)

蓝天白云123

import java.util.*;
public class Solution {
    public ArrayList<Interval> insert(ArrayList<Interval> intervals, Interval newInterval) {
        ArrayList<Interval> res = new ArrayList<>();
        if(intervals.isEmpty() && newInterval == null) {
            return res;
        }
        boolean b = false;  //记录新区间是否已经插入了，防止没有区间的start大于新区间的end的情况
        for(int i = 0;i < intervals.size();i++) {
            Interval inter = intervals.get(i);
            //如果当前区间与新区间无交集且新区间在右侧，直接收集当前区间
            if(inter.end < newInterval.start) {
                res.add(inter);
            }
            //如果新区间与当前区间无交集，且新区间在左侧，则将更新后的新区间收集，把剩下的区间也全部收集
            else if(inter.start > newInterval.end) {
                b = true;
                res.add(newInterval);
                for(int j = i;j < intervals.size();j++) {
                    res.add(intervals.get(j));
                }
                break;
            }
            else {  //如果当前区间与新区间有交集，更新新区间的两端。start二者取小，end取最大即可
                newInterval.start = Math.min(newInterval.start,inter.start);
                newInterval.end = Math.max(newInterval.end,inter.end);
            }
        }
        //如果更新的区间还没收集，则收集
        if(!b) {
            res.add(newInterval);
        }
        return res;
    }
}

时间O(n)，空间O(n)。为了方便用新集合收集区间了，改一改应该可以直接操作原集合，实现空间复杂度O(1)

发表于 2020-06-06 18:59:34 回复(0)

字节跳动内推请找我

public class Solution {
    /* 构建一个比较器   */
    Comparator<Interval> cmp = new Comparator<Interval>(){
        public int compare(Interval l1,Interval l2){
            if(l1.start > l2.start)
                return 1;
            else
                return -1;
        }
    };
    public ArrayList<Interval> insert(ArrayList<Interval> intervals, Interval newInterval) {
        ArrayList<Interval> res =new ArrayList<Interval>();
        for(Interval tmp:intervals){
            /*如果tmp与newInterval没有交集，就进入我们的结果集合中 */
            if(tmp.end<newInterval.start || tmp.start>newInterval.end)
                res.add(tmp);
            else {
            /* 如果tmp与newInterval有交集，我们就取他们的并集，取两个start的较小值，取end的较大值 */
                newInterval.start=Math.min(newInterval.start,tmp.start);
                newInterval.end=Math.max(newInterval.end,tmp.end);
            }
        }
        res.add(newInterval);
        /*测试用例需要排序好的集合，因此构造了一个比较器。*/
        res.sort(cmp);
        return res;
    }
}

发表于 2019-07-09 23:17:14 回复(0)

zbbsyx

// 先按照start升序插入 再合并
class Solution {
public:
    vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) {
        vector<Interval> res;
        int i = 0;
        bool insert = false;
        while(i < intervals.size()){
            if(newInterval.start < intervals[i].start){
                res.push_back(newInterval);
                insert = true;
            }
            res.push_back(intervals[i ++]);
        }
        if(!insert) res.push_back(newInterval);
        intervals.clear();
        intervals.push_back(res[0]);
        for(int i = 1; i < res.size(); i ++){
            int k = intervals.size() - 1;
            Interval interval = intervals[k];
            Interval newInterval = res[i];
            if(newInterval.start <= interval.end){
                if(newInterval.end >= interval.end){
                    intervals[k].end = newInterval.end;
                }
            }
            else{
                intervals.push_back(newInterval);
            }
        }
        return intervals;
    }
};

发表于 2019-04-23 10:09:18 回复(0)

chorifa

import java.util.*;

public class Solution {
    public ArrayList<Interval> insert(ArrayList<Interval> intervals, Interval newInterval) {
        int newStart = newInterval.start;
        int newEnd = newInterval.end;
        for(Iterator<Interval> it = intervals.iterator(); it.hasNext(); ){
            Interval tmp = it.next();
            if(tmp.start < newStart && tmp.end >= newStart) newStart = tmp.start; //这里判断的等号不能少，比如[1,2]和[2,3]
            if(tmp.start <= newEnd && tmp.end > newEnd) newEnd = tmp.end; // 同理等号不能少，如[2,3]和[1,2]
            if(tmp.start >= newStart && tmp.end <= newEnd) it.remove();
        }
        int lenOld = intervals.size();
        for(int index = 0; index < lenOld; index++) // 注意循环实际是不能遍历的，因为len变了，但只要找到一次即可
            if(intervals.get(index).start > newStart){
                intervals.add(index, new Interval(newStart,newEnd));
                break;
            }
        if(intervals.size() == lenOld) intervals.add(new Interval(newStart,newEnd)); // 这一条别忘了，可能加在末尾
        return intervals;
    }
}

发表于 2019-01-29 10:51:39 回复(0)

llch__

    public ArrayList<Interval> insert(ArrayList<Interval> intervals, Interval newInterval) {
        ArrayList<Interval> result = new ArrayList<Interval>();
        if(intervals.isEmpty()) {
        	result.add(newInterval);
        	return result;
        }
        int start = newInterval.start;
        int end = newInterval.end;
        
        boolean isAdd = false;
        for(int i=0; i<intervals.size(); i++){
        	Interval interval = intervals.get(i);
        	if(interval.end < start){
        		result.add(interval);
        		continue;
        	}
        	if(interval.start > end){
        		if(!isAdd){
            		result.add(new Interval(start, end));
            		isAdd = true;	
        		}
        		result.add(interval);
        		continue;
        	}
        	if(start>=interval.start && start <= interval.end){
        		start = interval.start;
        	}
        	if(end >= interval.start && end <= interval.end){
        		end = interval.end;
        	}
        }
        if(isAdd){
        	result.add(new Interval(start, end));
        }
        
        return result;
    }

发表于 2018-07-28 00:29:28 回复(0)

丶沉梦昂志

import java.util.*;
public class Solution {//此题借用了上一题merge-interval
    public ArrayList<Interval> insert(ArrayList<Interval> intervals, Interval newInterval) {
        intervals.add(newInterval);
        Collections.sort(intervals, new Comparator<Interval>() {
           
            public int compare(Interval o1, Interval o2) {
                return o1.start - o2.start;
            }
        });
        return merge(intervals);
    }

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

        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(Math.min(preStart, curStart), Math.max(preEnd, curEnd)));
                intervals.set(i - 1, null);
            }
        }

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

发表于 2017-11-22 19:25:52 回复(0)

微软内推小王子

采用Python内置的折半查找：

# Definition for an interval.
# class Interval(object):
#     def __init__(self, s=0, e=0):
#         self.start = s
#         self.end = e

import bisect

class KeyifyList(object):
    def __init__(self, inner, key):
        self.inner = inner
        self.key = key

    def __len__(self):
        return len(self.inner)

    def __getitem__(self, k):
        return self.key(self.inner[k])

class Solution(object):
    def insert(self, l, a):
        start = bisect.bisect_left(KeyifyList(l, lambda x: x.start), a.start) - 1
        end = bisect.bisect_right(KeyifyList(l, lambda x: x.end), a.end)

        if start >= 0:
            if l[start].end < a.start:
                start += 1
            else:
                a.start = l[start].start
        if end < len(l):
            if l[end].start > a.end:
                end -= 1
            else:
                a.end = l[end].end

        return (l[0:start] if start > 0 else []) + [a] + (l[end + 1:len(l)] if end + 1 < len(l) else [])

编辑于 2017-10-06 18:01:42 回复(0)

C/C++

nbgao

class Solution {
public:
    vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) {
        vector<Interval> result;
        for(auto i:intervals)
        {
            if(Fun(i, newInterval))
                result.push_back(i);
            else{
                newInterval.start = min(i.start, newInterval.start);
                newInterval.end = max(i.end, newInterval.end);             }         }         result.push_back(newInterval);         sort(result.begin(), result.end(), cmp);         return result;              }
    bool Fun(const Interval &a, const Interval &b)
    {
        return (a.end < b.start) || (b.end < a.start) ;     }     static bool cmp(const Interval &a, const Interval &b)     {         return a.start < b.start;     }
};

发表于 2017-10-01 01:19:58 回复(0)

廿四桥明月夜

bool comp(const Interval &i1, const Interval &i2)
{
    if(i1.start != i2.start)
        return i1.start < i2.start;
    else
        return i1.end < i2.end;
}

class Solution {
public:
    vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) {
        intervals.push_back(newInterval);
        sort(intervals.begin(), intervals.end(), comp);

        vector<Interval> res;
        res.push_back(intervals.front());

        int len = intervals.size();
        for(int i = 1; i < len; ++i){
            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;
    }
};
参考了xiao_lai的解法，略作改动

发表于 2016-12-28 09:49:04 回复(0)

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> insert(vector<Interval> &intervals, Interval newInterval) {
        //You may assume that the intervals were initially sorted according to their start times.
        intervals.push_back(newInterval);
        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:16:03 回复(0)

C/C++

ButterFlyEffect

写起来还有点复杂。

1 先二分找到比new.start小的那个区间；

2 插入后，再merge。

看到顺序遍历比较，逐个erase的代码，还更快一些😂。

/**
 * 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> insert(vector<Interval> &intervals, Interval newInterval) {
        // binary search insert position
        int l = 0, r = intervals.size()-1, index = -1;
        while(l <= r) {
            int mid = (l+r)/2;
            if(intervals[mid].start == newInterval.start) {
                index = mid;
                break;
            } else if(intervals[mid].start > newInterval.start) {
                r = mid - 1;
            } else if(intervals[mid].start < newInterval.start) {
                index = mid;
                l = mid + 1;
            }
        }
        int pos = 0;
        if(index < 0) { // no smaller
            intervals.insert(intervals.begin(), newInterval);
        } else {
            // merge
            if(newInterval.start <= intervals[index].end) {
                pos = index;
                intervals[index].end = max(newInterval.end, intervals[index].end);
            } else { // insert new
		intervals.insert(intervals.begin()+index+1, newInterval);
                pos = index+1;
            }
	    }
        // merge from index+1, overlapped by end
        int is = pos+1;
        int newe = intervals[pos].end;
        while(is < intervals.size()) {
            if(intervals[is].start > intervals[pos].end) break;
            newe = max(newe, intervals[is].end);
            is++;
        }
        intervals[pos].end = newe;
        intervals.erase(intervals.begin() + pos+1, intervals.begin() + is);
        return intervals;
    }
};

发表于 2020-11-10 10:06:40 回复(0)

好好学习11&面向简历编程

这道题有点像股票低买高卖获取最大收益的题目，从之前遍历的区间和当前区间找到要插入的左边界和右边界，一要遍历记录，二要值比较。

发表于 2020-11-04 22:03:07 回复(0)

C/C++

华科不平凡

循环遍历原有区间，将待插入区间的右端点、左端点分别与当前区间比较，并更新待插入区间的左右端点，代码如下：

//
// Created by jt on 2020/9/29.
//
#include <vector>
using namespace std;

class Solution {
public:
    vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) {
        vector<Interval> res;
        int i = 0;
        for (; i < intervals.size(); ++i) {
            // 如果新区间的右边界小于当前区间的左边界，终止循环
            // 如果新区间和当前区间有重叠，更新新区间的左右边界
            // 如果新区间的左边界大于当前区间的右边界，将当前区间放入结果
            if (newInterval.end < intervals[i].start) break;
            else if (newInterval.start <= intervals[i].end) {
                newInterval.start = min(newInterval.start, intervals[i].start);
                newInterval.end = max(newInterval.end, intervals[i].end);
            } else res.push_back(intervals[i]);
        }
        // 将更新后的新区间放入结果
        res.push_back(newInterval);
        // 将剩余的区间放入结果
        while(i < intervals.size()) {
            res.push_back(intervals[i]);
            ++i;
        }
        return res;
    }
};

发表于 2020-09-29 15:16:45 回复(0)

科学xx

public ArrayList<Interval> insert(ArrayList<Interval> intervals, Interval newInterval) {

//先插入排序再合并

intervals.add(newInterval);
Collections.sort(intervals, Comparator.comparingInt(a -> a.start));
ArrayList<Interval> res = new ArrayList<>();
res.add(intervals.get(0));
Interval pre;
Interval now;
for (int i = 1; i < intervals.size(); i++) {
pre = res.get(res.size()-1);
now = intervals.get(i);
if (pre.end < now.start){
res.add(now);
}else {
res.remove(pre);
res.add(new Interval(Math.min(pre.start,now.start),Math.max(pre.end,now.end)));
}
}
return res;
}

发表于 2020-08-30 16:53:38 回复(0)

C/C++

Pony_Bai

//首先把newInterval插入intervals中正确的位置，使intervals的所有元素都按start升序排列
//建立一个栈，遍历intervals，如果栈顶元素和intervals当前元素有重叠，更新栈顶元素，否则当前元素入栈

class Solution {
public:
    vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) {
        vector<Interval>res;
        int n=intervals.size();
        if(n==0)
        {
            res.push_back(newInterval);
            return res;
        }
        vector<Interval>::iterator iter=intervals.begin();
        for(;iter!=intervals.end();++iter)
        {
            if(iter->start>newInterval.start)
                break;
        }
        intervals.insert(iter,newInterval);
        res.push_back(intervals[0]);
        for(iter=intervals.begin()+1;iter!=intervals.end();++iter)
        {
            if(res.back().end>=iter->start)
                res.back().end=max(res.back().end,iter->end);
            else
                res.push_back(*iter);
        }
        return res;
        
    }
};

发表于 2020-06-03 12:30:14 回复(0)

插入区间

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题