Scalanie nakładających się interwałów II

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

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.

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.

Wywiady dotyczące projektowania systemu pękania
Translate »