시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.
병합 겹치는 간격 문제에서 우리는 간격 모음을 제공하고 모든 겹치는 간격을 병합하고 반환합니다.
차례
예
입력 : [[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이면 i 번째 간격을 선택하고 시작 및 종료 변수를 업데이트합니다.
- 이제 i 번째 간격이 이전에 선택한 간격과 겹치는 지 확인한 다음 이전 끝의 최대 값과 i 번째 간격의 끝으로 끝 변수를 수정합니다.
- 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이기 때문입니다.
