合并重叠间隔


难度级别 中等
经常问 土砖 亚马逊 Apple 彭博 思科 易趣 Facebook 高盛 谷歌 IXL 微软 神谕 Palantir Technologies 贝宝 Splunk的 广场 Twitter 尤伯杯 VMware的 Yandex的
排列 排序

在合并重叠间隔问题中,我们给出了一个间隔集合,合并并返回所有重叠间隔。

使用案列

输入:[[2,3],[3,4],[5,7]]

输出:[[2,4],[5,7]]

说明:

我们可以将[2,3]和[3,4]合并在一起形成[2,4]

合并重叠间隔

查找合并重叠间隔的方法

这里的想法是根据开始索引对间隔进行排序,以便我们可以通过跟踪每个合并间隔的开始索引和结束索引来合并它们。

如果我们有一个合并的间隔[a,b],下一个间隔是[c,d]。 因此,有以下三种情况:

  • 当c <= d并且d> = b时,结果间隔将为[a,d]

 

  • 当c <= d且d <= b时,结果间隔为[a,b]

  • 当c> d时,间隔不能合并,我们将得到两个结果间隔[a,b]和[c,d]

查找合并重叠间隔的算法

步骤1: 首先根据间隔的开始索引对间隔进行排序,然后根据其结束索引对间隔进行排序。 此步骤将花费(登录)时间。

步骤2: 将开始和结束变量初始化为-1,这表示当前没有间隔。

步骤3: 遍历间隔 排列 并检查以下三个条件:

  1. 如果开始和结束变量为-1,则选择第i个间隔并更新开始和结束变量。
  2. 现在检查ith间隔是否与先前选择的间隔重叠,然后使用ith间隔的前一个结束点和结束点的最大值来修改结束变量。
  3. 如果第ith个间隔与先前选择的间隔不重叠,则将前一个间隔推入ans数组,并用ith间隔更新开始和结束变量。

实施

C ++程序合并重叠间隔

#include<bits/stdc++.h>
using namespace std;
vector<vector<int>> merge(vector<vector<int>>& intervals) {
    sort(intervals.begin(),intervals.end());
    vector<vector<int>> ans;
    int i=0;
    int n=intervals.size(),s=-1,e=-1;
    while(i<n){
        if(s==-1){
            s=intervals[i][0];
            e=intervals[i][1];
            i++;
        }
        else{
            if(intervals[i][0]<=e){
                e=max(e,intervals[i][1]);
                i++;
            }
            else{
                ans.push_back(vector<int>{s, e});
                s=intervals[i][0];
                e=intervals[i][1];
                i++;
            }
        }
    }
    if(s!=-1){
        ans.push_back(vector<int>{s, e});
    }
    return ans;
}
int main(){
    int n;
    cin>>n;
    vector<vector<int>> intervals(n);
    for(int i=0;i<n;i++){
        int a,b;
        cin>>a>>b;
        intervals[i].push_back(a);
        intervals[i].push_back(b);
    }
    vector<vector<int>> ans = merge(intervals);
    cout<<"Intervals after merge operation are:\n";
    for(int i=0;i<ans.size();i++){
        cout<<ans[i][0]<<" "<<ans[i][1]<<"\n";
    }
}
4
1 3
2 6
8 10
15 18
Intervals after merge operation are:
1 6
8 10
15 18

合并重叠间隔的JAVA程序

import java.util.*;
public class Main
{
    public static int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (a,b)->Integer.compare(a[0],b[0]));
        ArrayList<int[]> list = new ArrayList();
        int i=0;
        int n=intervals.length,s=-1,e=-1;
        while(i<n){
            if(s==-1){
                s=intervals[i][0];
                e=intervals[i][1];
                i++;
            }
            else{
                if(intervals[i][0]<=e){
                    e=Math.max(e,intervals[i][1]);
                    i++;
                }
                else{
                    list.add(new int[]{s, e});
                    s=intervals[i][0];
                    e=intervals[i][1];
                    i++;
                }
            }
        }
        if(s!=-1){
            list.add(new int[]{s, e});
        }
        int[][] arr = new int[list.size()][2];
		return list.toArray(arr);
    }
	public static void main(String[] args) {
	    Scanner sc = new Scanner(System.in);
	    int n = sc.nextInt();
	    int[][] arr = new int[n][2];
	    for(int i=0;i<n;i++){
            arr[i][0] = sc.nextInt();
            arr[i][1] = sc.nextInt();
        }
        int[][] ans = merge(arr);
		System.out.println("Intervals after merge operation are:");
		for(int i=0;i<ans.length;i++){
		    System.out.println(ans[i][0]+" "+ans[i][1]);
		}
	}
}
5
1 2
2 5
2 6
7 9
15 18
Intervals after merge operation are: 
1 6 
7 9 
15 18

复杂度分析

时间复杂度

O(登录)

排序需要O(nlogn)时间,一次遍历数组需要O(n)时间。

因此,总时间复杂度为O(nlogn + n),即O(nlogn)

空间复杂度

O(n),因为我们使用向量存储结果,并且当所有间隔都重叠时,其最大大小为N。

參考資料