Қабаттасатын аралықтарды біріктіру


Күрделілік дәрежесі орта
Жиі кіреді Adobe Amazon алма Bloomberg Cisco еВау Facebook Голдман Сакс Google IXL Microsoft Oracle Palantir Technologies PayPal Splunk шаршы Twitter қиятын VMware Яндекс
Array Сұрыптау

Қабаттасатын аралықтарды біріктіру мәселесінде біз интервалдар жиынтығын бердік, барлық қабаттасқан аралықтарды біріктіріп, қайтарамыз.

мысал

Кіріс: [[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] болады

 

  • Ал с <= d және d <= b болғанда нәтижелік интервал [a, b] болады.

  • С> d болғанда, онда интервалдарды біріктіру мүмкін емес және бізде [a, b] және [c, d] нәтижелі екі интервал болады.

Біріктірілген қабаттасатын аралықтарды табу алгоритмі

Қадам 1: Аралықтарды алдымен олардың бастапқы индексі бойынша, содан кейін олардың соңғы индексі негізінде сұрыптаңыз. Бұл қадам (nlogn) уақытты алады.

Қадам 2: Бастапқы және аяқталатын айнымалыны -1 деп инициализациялаңыз, бұл қазіргі уақытта интервал алынбағанын көрсетеді.

Қадам 3: Аралық бойынша қайталаңыз массив және осы үш шартты тексеріңіз:

  1. Егер басталатын және аяқталатын айнымалы -1 болса, онда ith аралығын таңдап, басталатын және аяқталатын айнымалыны жаңартыңыз.
  2. Енді ith аралығы бұрын алынған интервалмен қабаттасып жатқанын тексеріп, соңғы айнымалыны алдыңғы аяқталудың максимумымен және ith интервалының соңымен өзгертіңіз.
  3. Егер ith аралығы бұрын алынған интервалмен қабаттаспаса, онда алдыңғы жиілікті ans массивіне итеріп, басталатын және аяқталатын айнымалыларды ith аралықтарымен жаңартыңыз.

Іске асыру

C ++ бағдарламасы біріктіру аралықтары

#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

Біріктірілген қабаттасуға арналған 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 болады.

Әдебиеттер тізімі