Pytania do rozmowy kwalifikacyjnej na temat projektowania systemu może być tak nieograniczona, że trudno jest określić właściwy sposób przygotowania. Teraz jestem w stanie złamać rundy projektowe Amazon, Microsoft i Adobe po zakupie ta książka. Codziennie poprawiaj jeden pytanie projektowe i obiecuję, że możesz złamać cały projekt.
Spis treści
Problem Statement
W zadaniu „Merge Overlapping Intervals II” podaliśmy zestaw interwały. Napisz program, który połączy nakładające się interwały w jeden i wydrukuje wszystkie nienakładające się przedziały.
Format wejściowy
Pierwszy wiersz zawierający liczbę całkowitą n.
Drugi wiersz zawierający n par, gdzie każda para oznacza przedział.
Format wyjściowy
Wydrukuj wszystkie nienakładające się przedziały, w których każdy przedział zawiera 2 wartości całkowite.
ograniczenia
- 1 <= n <= 10 ^ 5
- 1 <= pierwszy interwał <= drugi interwał <= 10 ^ 9
Przykład
4 1 3 2 6 8 10 15 18
1 6 8 10 15 18
Algorytm
Najpierw sortujemy wektor pary na podstawie pierwszej wartości. Teraz wstawiamy pierwszy przedział do naszej scalonej listy i kontynuujemy rozważanie każdego przedziału po kolei w następujący sposób: Jeśli bieżący przedział zaczyna się po zakończeniu poprzedniego, nie nakładają się one i możemy dołączyć bieżący przedział do scalonego. W przeciwnym razie nakładają się na siebie i łączymy je, aktualizując koniec poprzedniego interwału, jeśli jest mniejszy niż koniec bieżącego interwału.
Prosty dowód przez sprzeczność pokazuje, że ten algorytm zawsze daje poprawną odpowiedź. Po pierwsze, przypuśćmy, że algorytm w pewnym momencie nie łączy dwóch przedziałów, które powinny zostać połączone. Oznaczałoby to, że istnieje pewna trójka indeksów i, j, k na liście przedziałów ints, takich, że i <j <k i (a [i], a [k]) nie mogą być połączone, ale żadnego (a [ i], a [j]) lub (a [j], a [k]) mogą zostać połączone. Z tego scenariusza wynika kilka nierówności:
- a [i] .second
- a [j] .second
- a [i]. sekunda ≥a [k]. pierwsza
Realizacja
Program w 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;
}
Program Java
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
Analiza złożoności
Złożoność czasowa
O (nlogn) gdzie n to liczba podanych nam par / przedziałów. Tutaj wykonujemy sortowanie, które prowadzi nas do złożoności czasu nlogn.
Złożoność przestrzeni
Na) gdzie n to liczba nienakładających się przedziałów czasu na przechowywanie danych wyjściowych.
