Scal nakładające się przedziały

Poziom trudności Średni
Często zadawane pytania Adobe Amazonka Apple Bloomberg Cisco eBay Facebook Goldman Sachs Google IXL Microsoft wyrocznia Palantir Technologies PayPal Splunk Kwadratowe Twitter Uber VMware Yandex
Szyk Sortowanieodwiedzajacy 93

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.

W problemie scalania nakładających się interwałów podaliśmy zbiór przedziałów, scalamy i zwracamy wszystkie nakładające się przedziały.

Przykład

Wkład: [[2, 3], [3, 4], [5, 7]]

Produkcja: [[2, 4], [5, 7]]

Wyjaśnienie:

Możemy połączyć [2, 3] i [3, 4] razem, tworząc [2, 4]

Scal nakładające się przedziałyszpilka

Podejście do znajdowania nakładających się interwałów scalania

Pomysł polega na sortowaniu przedziałów na podstawie indeksu początkowego, abyśmy mogli je scalić, po prostu śledząc indeks początkowy i końcowy dla każdego łączonego przedziału.

Jeśli mamy scalony przedział [a, b], a następny przedział to [c, d]. Mamy więc trzy przypadki:

  • Gdy c <= d i d> = b, wynikowy przedział będzie miał postać [a, d]

 

  • A gdy c <= d i d <= b, to wynikowy przedział będzie miał postać [a, b]

szpilka

  • Gdy c> d, to przedziały nie mogą się łączyć i będziemy mieli dwa wypadkowe przedziały [a, b] i [c, d]

szpilka

Algorytm znajdowania nakładających się interwałów scalania

Krok 1: Posortuj przedziały najpierw na podstawie ich indeksu początkowego, a następnie na podstawie indeksu końcowego. Ten krok zajmie (nlogn) czasu.

Krok 2: Zainicjuj zmienną początkową i końcową jako -1, co oznacza, że ​​obecnie nie jest wybrany żaden interwał.

Krok 3: Powtarzaj interwał szyk i sprawdź te trzy warunki:

  1. Jeśli zmienną początkową i końcową jest -1, wybierz i-ty przedział i zaktualizuj zmienną początkową i końcową.
  2. Teraz sprawdź, czy i-ty przedział nakłada się na poprzednio wybrany przedział, a następnie zmodyfikuj zmienną końcową maksimum z poprzedniego końca i koniec i-tego przedziału.
  3. Jeśli i-ty przedział nie nakłada się na poprzednio wybrany przedział, to wsuń poprzedni przedział do tablicy ans i zaktualizuj zmienną początkową i końcową o i-ty przedział.

Realizacja

Program C ++ Scalanie nakładających się interwałów

#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

Program JAVA do łączenia nakładających się interwałów

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

Analiza złożoności

Złożoność czasowa

O (nlogn)

Sortowanie zajmuje O (nlogn) czasu, a przemierzanie tablicy raz zajmuje O (n) czasu.

Stąd całkowita złożoność czasowa wynosi O (nlogn + n) tj. O (nlogn)

Złożoność przestrzeni

O (n), ponieważ używamy wektora do przechowywania wyniku, a jego maksymalny rozmiar to N, gdy wszystkie przedziały pokrywają się.

Referencje

Wywiady dotyczące projektowania systemu pękania
Translate »