Спајање преклапајућих интервала  


Ниво тешкоће Средњи
Често питани у адобе амазонка јабука Блоомберг Цисцо еБаи фацебоок Голдман Сакс гоогле ИКСЛ мицрософт пророчанство Палантир Тецхнологиес ПаиПал Сплунк Квадрат твиттер Убер ВМваре иандек
Ред сортирање

У проблему спајања преклапајућих интервала дали смо збирку интервала, објединимо и вратимо све интервале који се преклапају.

Пример  

Улаз: [[2, 3], [3, 4], [5, 7]]

Излаз: [[2, 4], [5, 7]]

objašnjenje:

Можемо спојити [2, 3] и [3, 4] заједно да бисмо формирали [2, 4]

Спајање преклапајућих интервалаПин

Приступ за проналажење интервала који се преклапају  

Идеја је овде да се интервали сортирају на основу почетног индекса тако да их можемо спојити само праћењем почетног и крајњег индекса за сваки спојени интервал.

Ако имамо обједињени интервал [а, б], а следећи интервал је [ц, д]. Дакле, постоје три случаја:

  • Када је ц <= д и д> = б, тада би резултујући интервал био [а, д]

 

  • А када је ц <= д и д <= б, тада би резултујући интервал био [а, б]

Пин

  • Када је ц> д, тада се интервали не могу спојити и имаћемо два резултујућа интервала [а, б] и [ц, д]

Пин

Алгоритам за проналажење интервала који се преклапају  

Корак КСНУМКС: Интервале сортирајте прво на основу њиховог почетног индекса, а затим на основу њиховог завршног индекса. Овај корак ће потрајати (нлогн).

Корак КСНУМКС: Иницијализујте почетну и завршну променљиву као -1, то указује на то да тренутно нема покупљеног интервала.

Корак КСНУМКС: Понављајте током интервала поредак и проверите ова три услова:

  1. Ако је почетна и завршна променљива -1, изаберите и-ти интервал и ажурирајте почетну и завршну променљиву.
  2. Сада проверите Да ли се и-ти интервал преклапа са претходно одабраним интервалом, модификујте завршну променљиву са максимумом претходног завршетка и краја и-тог интервала.
  3. Ако се и-ти интервал не преклапа са претходно одабраним интервалом, притисните претходни интервал у низу анс и ажурирајте почетну и завршну променљиву са и-им интервалом.
Види такође
Претворите БСТ у бинарно стабло тако да се сваком кључу дода збир свих већих кључева

Имплементација  

Интервали преклапања програма спајања програма Ц ++

#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

ЈАВА програм за спајање преклапајућих интервала

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

Анализа сложености  

Сложеност времена

О (нлогн)

За сортирање је потребно О (нлогн) време, а за обилазак низа једном потребно је О (н) време.

Отуда је укупна временска сложеност О (нлогн + н), тј. О (нлогн)

Сложеност простора

О (н) јер користимо вектор за чување резултата и његова максимална величина је Н када се сви интервали преклапају.

Референце