ຮວມໄລຍະຊ້ອນກັນ  


ລະດັບຄວາມຫຍຸ້ງຍາກ ຂະຫນາດກາງ
ຖາມເລື້ອຍໆໃນ Adobe Amazon ຈາກຫນາກແອບເປີ Bloomberg Cisco eBay ເຟສບຸກ Goldman Sachs ກູໂກ IXL Microsoft Oracle Palantir Technologies PayPal ແຕກອອກ Square Twitter Uber VMware Yandex
Array ຮຽງລໍາດັບ

ໃນການລວມບັນຫາໄລຍະຫ່າງກັນພວກເຮົາໄດ້ໃຫ້ການລວບລວມໄລຍະຫ່າງ, ຮວມເຂົ້າກັນແລະສົ່ງຄືນທຸກໆໄລຍະທີ່ຊໍ້າຊ້ອນ.

ຍົກຕົວຢ່າງ  

ການປ້ອນຂໍ້ມູນ: [[2, 3], [3, 4], [5, 7]]

ຜົນໄດ້ຮັບ: [[2, 4], [5, 7]]

ຄໍາອະທິບາຍ:

ພວກເຮົາສາມາດລວມເຂົ້າກັນ [2, 3] ແລະ [3, 4] ຮ່ວມກັນເພື່ອປະກອບ [2, 4]

ຮວມໄລຍະຊ້ອນກັນPin

ວິທີການໃນການຊອກຫາໄລຍະຫ່າງກັນ  

ແນວຄວາມຄິດໃນທີ່ນີ້ແມ່ນການຈັດຮຽງໄລຍະຫ່າງໂດຍອີງໃສ່ດັດສະນີເລີ່ມຕົ້ນເພື່ອໃຫ້ພວກເຮົາສາມາດລວມເຂົ້າກັນໄດ້ໂດຍພຽງແຕ່ຕິດຕາມດັດສະນີຈຸດເລີ່ມຕົ້ນແລະຈຸດສຸດທ້າຍ ສຳ ລັບທຸກໆໄລຍະຫ່າງກັນ.

ຖ້າພວກເຮົາມີໄລຍະຫ່າງກັນ [a, b] ແລະໄລຍະຫ່າງຕໍ່ໄປແມ່ນ [c, d]. ສະນັ້ນມີສາມກໍລະນີ:

  • ເມື່ອ c <= d ແລະ d> = b ຫຼັງຈາກນັ້ນໄລຍະຫ່າງຂອງຜົນໄດ້ຮັບຈະເປັນ [a, d]

 

  • ແລະເມື່ອ c <= d ແລະ d <= b ຫຼັງຈາກນັ້ນໄລຍະຫ່າງຂອງຜົນໄດ້ຮັບຈະເປັນ [a, b]

Pin

  • ໃນເວລາທີ່ c> d, ຫຼັງຈາກນັ້ນໄລຍະຫ່າງບໍ່ສາມາດລວມເຂົ້າກັນໄດ້ແລະພວກເຮົາຈະມີສອງໄລຍະຜົນທີ່ເກີດຂື້ນ [a, b] ແລະ [c, d]

Pin

ສູດການຄິດໄລ່ ສຳ ລັບການຊອກຫາ Merge Overlapping Intervals  

ຂັ້ນຕອນທີ 1: ຮຽງໄລຍະຫ່າງກ່ອນໂດຍອີງໃສ່ດັດຊະນີເລີ່ມຕົ້ນຂອງພວກເຂົາແລະຫຼັງຈາກນັ້ນອີງໃສ່ດັດສະນີສິ້ນສຸດຂອງພວກເຂົາ. ບາດກ້າວນີ້ຈະໃຊ້ເວລາ (ບໍ່ມີສະຕິ).

ຂັ້ນຕອນທີ 2: ເລີ່ມຕົ້ນຕົວປ່ຽນເລີ່ມຕົ້ນແລະສິ້ນສຸດເປັນ -1, ນີ້ຊີ້ໃຫ້ເຫັນວ່າປະຈຸບັນບໍ່ມີໄລຍະຫ່າງທີ່ຖືກເກັບ.

ຂັ້ນຕອນທີ 3: Iterate ໃນໄລຍະຫ່າງ array ແລະກວດເບິ່ງສາມເງື່ອນໄຂດັ່ງນີ້:

  1. ຖ້າຕົວປ່ຽນເລີ່ມຕົ້ນແລະສິ້ນສຸດແມ່ນ -1, ຫຼັງຈາກນັ້ນເລືອກເອົາໄລຍະຫ່າງຂອງ ith ແລະປັບປຸງຕົວປ່ຽນເລີ່ມຕົ້ນແລະສິ້ນສຸດ.
  2. ຕອນນີ້ໃຫ້ກວດເບິ່ງວ່າຖ້າໄລຍະຫ່າງຂອງ ith ຊ້ອນກັນກັບໄລຍະຫ່າງທີ່ເກັບໄວ້ກ່ອນ ໜ້າ ນີ້ຫຼັງຈາກນັ້ນໃຫ້ດັດແປງຕົວປ່ຽນສິ້ນສຸດດ້ວຍຈຸດສູງສຸດຂອງສິ້ນສຸດທ້າຍແລະສິ້ນສຸດຂອງໄລຍະຫ່າງຂອງ ith.
  3. ຖ້າໄລຍະຫ່າງຂອງ ith ບໍ່ຊ້ ຳ ຊ້ອນກັບໄລຍະຫ່າງທີ່ເກັບໄວ້ກ່ອນ ໜ້າ ນີ້ແລ້ວກົດໄລຍະຫ່າງກ່ອນ ໜ້າ ນີ້ໃນແຖວ array ແລະປັບປຸງຕົວປ່ຽນເລີ່ມຕົ້ນແລະສິ້ນສຸດດ້ວຍໄລຍະຫ່າງ ith.
ເບິ່ງ
ປ່ຽນ BST ໄປເປັນ Binary Tree ດັ່ງກ່າວລວມຍອດທີ່ໃຫຍ່ກວ່າທັງ ໝົດ ຈະຖືກເພີ່ມໃສ່ທຸກໆກຸນແຈ

ການປະຕິບັດ  

ໂປຣແກຣມ 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 ສຳ ລັບ Merge Overlapping Intervals

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) ເພາະວ່າພວກເຮົາໃຊ້ vector ເພື່ອເກັບຮັກສາຜົນໄດ້ຮັບແລະຂະ ໜາດ ສູງສຸດຂອງມັນແມ່ນ N ເມື່ອໄລຍະຫ່າງທັງ ໝົດ ຖືກທັບຊ້ອນ.

ເອກະສານ