겹치는 간격 병합

난이도 중급
자주 묻는 질문 어도비 벽돌 아마존 Apple 블룸버그 게시물에서 시스코 이베이 Facebook 골드만 삭스 구글 IXL Microsoft 신탁 Palantir Technologies 페이팔 스플 렁크 사각형. Twitter 동네 짱 VM웨어 Yandex 주차
배열 정렬조회수 36

병합 겹치는 간격 문제에서 우리는 간격 모음을 제공하고 모든 겹치는 간격을 병합하고 반환합니다.

입력 : [[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]를 갖게됩니다.

Merge Overlapping Interval을 찾는 알고리즘

1 단계 : 먼저 시작 인덱스를 기준으로 간격을 정렬 한 다음 종료 인덱스를 기준으로 정렬합니다. 이 단계는 (nlogn) 시간이 걸립니다.

2 단계 : 시작 및 종료 변수를 -1로 초기화합니다. 이는 현재 선택된 간격이 없음을 나타냅니다.

3 단계 : 간격 동안 반복 정렬 다음 세 가지 조건을 확인하십시오.

  1. 시작 및 종료 변수가 -1이면 i 번째 간격을 선택하고 시작 및 종료 변수를 업데이트합니다.
  2. 이제 i 번째 간격이 이전에 선택한 간격과 겹치는 지 확인한 다음 이전 끝의 최대 값과 i 번째 간격의 끝으로 끝 변수를 수정합니다.
  3. i 번째 간격이 이전에 선택한 간격과 겹치지 않으면 ans 배열에서 이전 간격을 푸시하고 시작 및 종료 변수를 i 번째 간격으로 업데이트합니다.

실시

C ++ 프로그램 Merge Overlapping Intervals

#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

Merge Overlapping Intervals를위한 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 (nlogn)

정렬에는 O (nlogn) 시간이 걸리고 배열을 한 번 순회하는 데 O (n) 시간이 걸립니다.

따라서 총 시간 복잡도는 O (nlogn + n) 즉, O (nlogn)입니다.

공간 복잡성

O (n)은 벡터를 사용하여 결과를 저장하고 모든 간격이 겹칠 때 최대 크기가 N이기 때문입니다.

참조

Translate »