Üst-üstə düşən fasilələri birləşdirin II

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Çiy kərpic Amazon alma Bloomberg Cisco eBay Facebook Goldman Sachs google IXL microsoft Kahin Palantir Texnologiyaları PayPal Kvalifikasiya Salesforce Boşalmaq cuqquldamaq Über VMware Walmart Laboratoriyaları Yahoo Yandex
Geyim çeşidləyiciBaxılıb 477

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

Problem bəyanat

"Çakışan Aralıqları Birləşdirmə II" problemində bir sıra verdik intervalları. Üst-üstə düşən aralıqları bir-birinə birləşdirəcək və üst-üstə düşməyən bütün aralıqları çap edəcək bir proqram yazın.

Giriş Formatı

Bir n tam ədədi olan ilk sətir.

Hər cütün intervalını ifadə etdiyi n cütlüyü olan ikinci sətir.

Çıxış formatı

Hər intervalın 2 tam dəyər olduğu bütün üst-üstə düşməyən fasilələri çap edin.

Məhdudiyyətlər

  • 1 <= n <= 10 ^ 5
  • 1 <= aralıq birinci <= aralıq ikinci <= 10 ^ 9

misal

4
1 3 2 6 8 10 15 18
1 6 
8 10 
15 18

Alqoritm

Əvvəlcə cütlüyün vektorunu ilk dəyər əsasında sıralayırıq. İndi ilk aralığı birləşdirilmiş siyahımıza əlavə edirik və hər bir aralığı növbə ilə aşağıdakı kimi nəzərdən keçirməyə davam edirik: Mövcud aralıq əvvəlki aralıq bitdikdən sonra başlayırsa, üst-üstə düşmür və cari aralığı birləşdirilmiş hala əlavə edə bilərik. Əks təqdirdə üst-üstə düşürlər və cari intervalın sonundan az olduqda əvvəlki intervalın sonunu yeniləyərək onları birləşdiririk.

Ziddiyyətə əsaslanan sadə bir dəlil bu alqoritmin hər zaman düzgün cavabı verdiyini göstərir. Birincisi, fərz edək ki, alqoritm bir nöqtədə birləşdirilməli olan iki fasiləni birləşdirə bilmir. Bu, i <j <k və (a [i], a [k]) birləşdirilə bilməyəcəyi qədər aralıq ints siyahısında üç, üç, üç, üç, üç, üç, üç, üç, üçlü göstəricilərin olduğunu göstərir, lakin nə (a [ i], a [j]) və ya (a [j], a [k]) birləşdirilə bilər. Bu ssenaridən bir neçə bərabərsizliyi izləyin:

  • a [i]. ikinci
  • a [j]. ikinci
  • a [i]. saniyə [k]. birincisi

Həyata keçirilməsi

C ++ Proqramı

#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;
}

Java Proqramı

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

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (nlogn) burada n bizə verilən cüt / fasilələrin sayıdır. Burada bizi nlogn zaman mürəkkəbliyinə aparan çeşidləmə aparırıq.

Kosmik Mürəkkəblik

O (n) burada n - nəticəni saxlamaq üçün üst-üstə düşməyən fasilələrin sayı.

Crack Sistemi Dizayn Müsahibələri
Translate »