겹치는 간격 병합 II

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

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

문제 정책

“Merge Overlapping Intervals II”문제에서 우리는 간격. 겹치는 간격을 하나로 병합하고 겹치지 않는 모든 간격을 인쇄하는 프로그램을 작성하십시오.

입력 형식

정수 n을 포함하는 첫 번째 줄입니다.

각 쌍이 간격을 나타내는 n 쌍을 포함하는 두 번째 줄.

출력 형식

각 간격이 2 개의 정수 값을 포함하는 모든 겹치지 않는 간격을 인쇄합니다.

제약

  • 1 <= n <= 10 ^ 5
  • 1 <= 첫 번째 간격 <= 두 번째 간격 <= 10 ^ 9

4
1 3 2 6 8 10 15 18
1 6 
8 10 
15 18

암호알고리즘

먼저 첫 번째 값을 기준으로 쌍의 벡터를 정렬합니다. 이제 병합 된 목록에 첫 번째 간격을 삽입하고 다음과 같이 각 간격을 차례로 고려합니다. 이전 간격이 끝난 후 현재 간격이 시작되면 겹치지 않으며 병합에 현재 간격을 추가 할 수 있습니다. 그렇지 않으면 겹치며 현재 간격의 끝보다 작 으면 이전 간격의 끝을 업데이트하여 병합합니다.

모순에 의한 간단한 증명은이 알고리즘이 항상 정답을 생성 함을 보여줍니다. 먼저, 어떤 지점에서 알고리즘이 병합해야하는 두 개의 간격을 병합하지 못한다고 가정합니다. 이것은 i <j <k 및 (a [i], a [k])가 병합 될 수 있지만 둘 다 (a [ i], a [j]) 또는 (a [j], a [k])는 병합 될 수 있습니다. 이 시나리오에서 몇 가지 부등식을 따릅니다.

  • a [i] .second
  • a [j] .second
  • a [i] .second≥a [k] .first

실시

C ++ 프로그램

#include <bits/stdc++.h>
using namespace std;

void merge(vector<pair<int,int>> &intervals) 
{
    sort(intervals.begin(), intervals.end());
    vector<pair<int,int>> merged;
    for(auto interval : intervals) 
    {
        if(merged.empty() || merged.back().second < interval.first) {
            merged.push_back({interval});
        }
        else 
        {
            merged.back().second = max(merged.back().second, interval.second);
        }
    }
    for(auto u: merged)
    {
        cout<<u.first<<" "<<u.second<<endl;
    }
}
    
int main()
{
   int n;
   cin>>n;
   vector<pair<int,int>> a;
   for(int i=0;i<n;i++)
   {
       int x,y;
       cin>>x>>y;
       a.push_back({x,y});
   }
   merge(a);
   return 0;
}

자바 프로그램

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Scanner;
class sum
{
    public static void merge(int[][] intervals) 
    {
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
        LinkedList<int[]> merged = new LinkedList<>();
        for (int[] interval : intervals) 
        {
            if (merged.isEmpty() || merged.getLast()[1] < interval[0]) 
            {
                merged.add(interval);
            }
            else 
            {
                merged.getLast()[1] = Math.max(merged.getLast()[1], interval[1]);
            }
        }
        merged.toArray(new int[merged.size()][]);
        for(int i=0;i<merged.size();i++)
        {
            System.out.println(merged.get(i)[0]+" "+merged.get(i)[1]);
        }
    }
    public static void main(String[] args)
    {
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int a[][] = new int [n][2];
        for(int i=0;i<n;i++)
        {
            a[i][0] = sr.nextInt();
            a[i][1] = sr.nextInt();
        }
        merge(a);
    }
}
2
1 4 3 6
1 6

복잡성 분석

시간 복잡성

O (nlogn) 여기서 n은 우리에게 주어진 쌍 / 간격의 수입니다. 여기서 우리는 nlogn 시간 복잡성으로 이끄는 정렬을 수행합니다.

공간 복잡성

O (N) 여기서 n은 출력을 저장할 겹치지 않는 간격의 수입니다.

균열 시스템 설계 인터뷰
Translate »