ઓવરલેપિંગ અંતરાલો મર્જ કરો


મુશ્કેલી સ્તર મધ્યમ
વારંવાર પૂછવામાં આવે છે એડોબ એમેઝોન સફરજન બ્લૂમબર્ગ સિસ્કો ઇબે ફેસબુક ગોલ્ડમૅન સૅશ Google આઈએક્સએલ માઈક્રોસોફ્ટ ઓરેકલ પાલાનિર ટેકનોલોજીસ પેપાલ સ્પ્લંક સ્ક્વેર Twitter ઉબેર વીએમવેર યાન્ડેક્ષ
અરે સોર્ટિંગ

મર્જ ઓવરલેપિંગ અંતરાલોની સમસ્યામાં આપણે અંતરાલોનો સંગ્રહ આપ્યો છે, મર્જ કરીને બધા ઓવરલેપિંગ અંતરાલો પાછા આપીએ છીએ.

ઉદાહરણ

ઇનપુટ: [[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] હશે

 

  • અને જ્યારે c <= d અને d <= b હોય ત્યારે પરિણામ અંતરાલ હશે [a, b]

  • જ્યારે સી> ડી, પછી અંતરાલો મર્જ કરી શકાતા નથી અને આપણી પાસે બે પરિણામી અંતરાલ હશે [એ, બી] અને [સી, ડી]

મર્જ ઓવરલેપિંગ અંતરાલો શોધવા માટે અલ્ગોરિધમ

પગલું 1: પહેલા તેમના પ્રારંભિક અનુક્રમણિકાના આધારે અંતરાલો સortર્ટ કરો અને પછી તેમના અંતિમ અનુક્રમણિકાના આધારે. આ પગલું (nlogn) સમય લેશે.

પગલું 2: પ્રારંભિક અને અંતિમ ચલ -1 તરીકે પ્રારંભ કરો, આ સૂચવે છે કે હાલમાં કોઈ અંતરાલ લેવામાં આવ્યું નથી.

પગલું 3: અંતરાલ ઉપર ભરો એરે અને આ ત્રણ શરતો તપાસો:

  1. જો પ્રારંભ અને અંતિમ ચલ -1 છે, તો પછી ith અંતરાલ પસંદ કરો અને પ્રારંભિક અને અંતિમ ચલને અપડેટ કરો.
  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

જટિલતા વિશ્લેષણ

સમય જટિલતા

ઓ (નોલોગ)

સortર્ટિંગમાં O (nlogn) સમય લાગે છે અને એરેના ટ્રાવર્સલને એકવાર O (n) સમય લાગે છે.

તેથી કુલ સમય જટિલતા માટે ઓ (nlogn + n) એટલે કે, O (nlogn) છે

અવકાશ જટિલતા

ઓ (એન) કારણ કે અમે પરિણામ સંગ્રહિત કરવા માટે વેક્ટરનો ઉપયોગ કરીએ છીએ અને જ્યારે તમામ અંતરાલો ઓવરલેપ થાય છે ત્યારે તેનું મહત્તમ કદ એન છે.

સંદર્ભ