首页 > 试题广场 >

插入区间

[编程题]插入区间

热度指数：1739 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个无重叠的，按照区间起点升序排列的区间列表，在列表中插入一个新区间，如果有原区间有重合，则合并，请返回插入后的区间列表。

数据范围：区间列表长度满足 $0 \le n \le 10^4 \$ ，区间的左右端点满足 $0 \le l,r \le 10^5 \$

示例1

输入

[[2,5],[6,11]],[5,6]

输出

[[2,11]]

示例2

输入

[],[2,5]

输出

[[2,5]]

算法知识视频讲解

Java

pein531

一个比较容易想到的思路是：先将新的区间连同原有的区间放到一个容器里，然后按区间的起点升序，且终点也升序进行二次排序，保证对于起点相同的区间而言，大区间排在后面。排好序后就可以对容器中的区间进行合并，遍历容器，不断将当前要加入到结果集中的区间与结果集中的最后一个区间进行对比，两者有重合区域时就将结果集的末尾区间修改成范围更大的。

import java.util.*;

/*
 * public class Interval {
 *   int start;
 *   int end;
 *   public Interval(int start, int end) {
 *     this.start = start;
 *     this.end = end;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param Intervals Interval类一维数组 
     * @param newInterval Interval类 
     * @return Interval类一维数组
     */
    public Interval[] insertInterval (Interval[] Intervals, Interval newInterval) {
        // write code here
        if(Intervals.length == 0){
            return new Interval[]{newInterval};
        }
        ArrayList<Interval> list = new ArrayList<>();
        list.add(newInterval);
        for(int i = 0; i < Intervals.length; i++){
            list.add(Intervals[i]);
        }
        // 先对所有区间按起点升序终点也升序进行二次排序，这样可以保证相同起点的区间，更大的区间在后面
        Collections.sort(list, (a, b) -> a.start != b.start? a.start - b.start: a.end - b.end);
        // 用双端链表构建一个结果集
        LinkedList<Interval> linkedlist = new LinkedList<>();
        linkedlist.add(list.get(0));
        for(int i = 1; i < list.size(); i++){
            if(list.get(i).start <= linkedlist.getLast().end){
                // 当前区间与最后一个加入的区间有重叠
                if(list.get(i).end <= linkedlist.getLast().end){
                    // 当前区间已经被前面的区间囊括
                    continue;
                }
                // 合并区间
                list.get(i).start = linkedlist.getLast().start;
                linkedlist.removeLast();
                linkedlist.add(list.get(i));
            }else{
                linkedlist.add(list.get(i));
            }
        }
        Interval[] res = new Interval[linkedlist.size()];
        Iterator<Interval> iterator = linkedlist.iterator();
        int index = 0;
        while(iterator.hasNext()){
            res[index++] = iterator.next();
        }
        return res;
    }
}

发表于 2021-12-11 14:54:06 回复(0)

C++

感谢靓仔赏饭吃

/**
 * struct Interval {
 *	int start;
 *	int end;
 *	Interval(int s, int e) : start(start), end(e) {}
 * };
 */
#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param Intervals Interval类vector 
     * @param newInterval Interval类 
     * @return Interval类vector
     */
    vector<Interval> insertInterval(vector<Interval>& Intervals, Interval newInterval) {
    vector<Interval>ans;  
    if(Intervals.empty()){
    ans.push_back(newInterval);
    return ans;    
    }  
    Intervals.push_back(newInterval);
    sort(Intervals.begin(),Intervals.end(),[](Interval a,Interval b){return a.start<b.start;});
    for(int i=0;i<Intervals.size()-1;i++){
        Interval temp=Intervals[i];
        while(temp.end>=Intervals[i+1].start){
            temp.end=max(temp.end,Intervals[i+1].end);
            i++;
        }
        ans.push_back(temp);
    }
    if(ans.back().end>=Intervals.back().end){
        return ans;
    }else{
        ans.push_back(Intervals.back());
        return ans;
    }
    }
};

编辑于 2024-04-19 13:52:16 回复(0)

Python 3

liangzhengjie

class Solution:
    def insertInterval(self , Intervals: List[Interval], newInterval: Interval) -> List[Interval]:
        # write code here
        if len(Intervals) == 0:
            return [newInterval]

        res  = []
        res.append(Intervals[0])

        selected = False
        for i in range(len(Intervals)):
            if not selected:
                if self.is_interval_intersect(newInterval, res[-1]):
                    res[-1].start = min(res[-1].start, newInterval.start)
                    res[-1].end = max(res[-1].end, newInterval.end)
                    selected = True

            if self.is_interval_intersect(res[-1], Intervals[i]):
                res[-1].start = min(res[-1].start, Intervals[i].start)
                res[-1].end = max(res[-1].end, Intervals[i].end)
            else:
                res.append(Intervals[i])

        if not selected:
            res.append(newInterval)

        return res

    def is_interval_intersect(self, i1, i2):
        a1,b1 = i1.start,i1.end
        a2,b2 = i2.start,i2.end

        if a1 <= a2 <= b1&nbs***bsp;a1 <= b2 <= b1&nbs***bsp;a2 <= a1 <= b2:
            return True
        else:
            return False

发表于 2024-04-01 22:45:05 回复(0)

牛客2024007号

import java.util.*;

/*
 * public class Interval {
 *   int start;
 *   int end;
 *   public Interval(int start, int end) {
 *     this.start = start;
 *     this.end = end;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param Intervals Interval类一维数组 
     * @param newInterval Interval类 
     * @return Interval类一维数组
     */
    public Interval[] insertInterval (Interval[] Intervals, Interval newInterval) {
        // write code here
        Arrays.sort(Intervals, (i1, i2) -> {
            if(i1.start == i2.start) {
                return i1.end - i2.end;
            }
            return i1.start - i2.start;
        });
        int start = newInterval.start;
        int end = newInterval.end;
        List<Interval> list = new ArrayList<>();

        int i = 0;
        for(; i < Intervals.length; i++) {
            Interval in = Intervals[i];
                // 不能合并
            if(start > in.end || end < in.start) {
                list.add(new Interval(in.start, in.end));
                continue;
            }else {
                start = Math.min(start, in.start);
                end = Math.max(end, in.end);
            }
        }
        list.add(new Interval(start, end));
        Interval[] res = new Interval[list.size()];
        for(int j = 0; j < res.length; j++) {
            res[j] = list.get(j);
        }
        Arrays.sort(res, (i1, i2) -> {
            if(i1.start == i2.start) {
                return i1.end - i2.end;
            }
            return i1.start - i2.start;
        });
        return res;
    }
}

编辑于 2024-02-10 14:16:46 回复(0)

四季豆&兰花草

有多少人和我一样没有看明白题目是什么意思的?

发表于 2022-08-01 10:40:42 回复(0)

Java

阿尔的阳光y

class Solution {
	public Interval[] insertInterval (Interval[] intervals, Interval newInterval){
		ArrayList<Interval> list = new ArrayList<>();

		for (Interval interval : intervals) {
			if (newInterval.end < interval.start || newInterval.start > interval.end){
				list.add(interval);
			}else {
				newInterval.start = Math.min(newInterval.start, interval.start);
				newInterval.end = Math.max(newInterval.end, interval.end);
			}
		}

		list.add(newInterval);
		Interval[] array = list.toArray(new Interval[0]);

		Arrays.sort(array, (o1, o2) -> o1.start - o2.start);
		return array;
	}

}

Java解法不相交区间正在加在返回结果中相交的区间取[min(L1, L2), max(R1, R2)]即可

发表于 2022-04-06 20:55:33 回复(0)

C++

Acmen_沉梦昂志

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param Intervals Interval类vector 
     * @param newInterval Interval类 
     * @return Interval类vector
     */
    vector<Interval> insertInterval(vector<Interval>& Intervals, Interval newInterval) {
        // write code here
        int i = 0;
        int n = Intervals.size();
        int s = newInterval.start , e = newInterval.end;
        vector<Interval> res;
        while(i < n && Intervals[i].end < s){
            res.push_back(Intervals[i]);
            i++;
        } 
        res.push_back(newInterval);
        while(i < n && res.back().end >= Intervals[i].start){
            
            res.back().start = min(Intervals[i].start,res.back().start);
            res.back().end = max(Intervals[i].end,res.back().end);
            i++;
        }
        while(i < n) {res.push_back(Intervals[i]);i++;}
        return res;
        
    }
};

发表于 2022-03-05 16:20:30 回复(0)

Java

除了吃还会干嘛

import java.util.*;

/*
 * public class Interval {
 *   int start;
 *   int end;
 *   public Interval(int start, int end) {
 *     this.start = start;
 *     this.end = end;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param Intervals Interval类一维数组 
     * @param newInterval Interval类 
     * @return Interval类一维数组
     */
    public Interval[] insertInterval (Interval[] Intervals, Interval newInterval) {
        // write code here
        if(Intervals.length == 0){
            return new Interval[]{newInterval};
        }
        ArrayList<Interval> list = new ArrayList<>();
        list.add(newInterval);
        for(int i = 0; i < Intervals.length; i++){
            list.add(Intervals[i]);
        }
        // 先对所有区间按起点升序终点也升序进行二次排序，这样可以保证相同起点的区间，更大的区间在后面
        Collections.sort(list, (a, b) -> a.start != b.start? a.start - b.start: a.end - b.end);
        // 用双端链表构建一个结果集
        LinkedList<Interval> linkedlist = new LinkedList<>();
        linkedlist.add(list.get(0));
        for(int i = 1; i < list.size(); i++){
            if(list.get(i).start <= linkedlist.getLast().end){
                // 当前区间与最后一个加入的区间有重叠
                if(list.get(i).end <= linkedlist.getLast().end){
                    // 当前区间已经被前面的区间囊括
                    continue;
                }
                // 合并区间
                list.get(i).start = linkedlist.getLast().start;
                linkedlist.removeLast();
                linkedlist.add(list.get(i));
            }else{
                linkedlist.add(list.get(i));
            }
        }
        Interval[] res = new Interval[linkedlist.size()];
        Iterator<Interval> iterator = linkedlist.iterator();
        int index = 0;
        while(iterator.hasNext()){
            res[index++] = iterator.next();
        }
        return res;
    }
}

发表于 2021-12-28 22:02:36 回复(0)