시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 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은 출력을 저장할 겹치지 않는 간격의 수입니다.
