Merge All Overlapping Intervals

#include<vector>

vector<vector<int>> mergeOverlappingIntervals(vector<vector<int>> &arr){

    // Write your code here.

    int n=arr.size();

    sort(arr.begin(),arr.end());

    vector<vector<int>>  ans;

    for(int i=0;i<n;i++)

    {

       if(ans.empty() || arr[i][0] > ans.back()[1])

       {

           ans.push_back(arr[i]);

       }

       else{

           ans.back()[1]=max(ans.back()[1],arr[i][1]);

       }

    }

    return ans;

}

import java.util.*;

import java.util.PriorityQueue;

public class Solution {

    public static List< List< Integer > > mergeOverlappingIntervals(int [][]arr){

        // Write your code here.

        List<List<Integer>> list = new ArrayList<>();

        int i=0,j=1;

        for(i=0;i<arr.length;i++){

            List<Integer> list1 = new ArrayList<>();

            list1.add(arr[i][0]);

            list1.add(arr[i][1]);

            list.add(list1);

        }

        i=0;

        Collections.sort(list,(a,b)->a.get(0)==b.get(0)?a.get(1)-b.get(1):a.get(0)-b.get(0));

        while(i<j && j<list.size()){

            List<Integer> l1 = list.get(i); 

            List<Integer> l2 = list.get(j);

            if(l1.get(1)>=l2.get(0) && l1.get(1)>=l2.get(1)){

                list.remove(j);

            }else if(l1.get(1)>=l2.get(0) && l1.get(1)<=l2.get(1)){

                l1.set(1,l2.get(1));

                list.set(i,l1);

                list.remove(j);

            }else{

                i++;

                j++;

            }

        }

        return list;

    }

}

#include<vector>

vector<vector<int>> mergeOverlappingIntervals(vector<vector<int>> &arr){

    // Write your code here.

    int n = arr.size();

    sort(arr.begin(), arr.end());

    vector<vector<int>> ans;

    for(int i = 0;i < n;i++){

        if(ans.empty() || arr[i][0] > ans.back()[1]){

            ans.push_back(arr[i]);

        }

        else{

            ans.back()[1] = max(ans.back()[1] , arr[i][1]);

        }

    }

    return ans;

}

public static List< List< Integer > > mergeOverlappingIntervals(int [][]arr){

        int n = arr.length;

        int l1 = arr[0][0];

        int r1 = arr[0][1];

        List<List<Integer>> anslist = new ArrayList<>();

        for(int i=0; i<n; i++){

            int l2 = arr[i][0];

            int r2 = arr[i][1];

            if(l2<=r1){

                r1 = Math.max(r2, r1);

            }

            else{

                anslist.add(Arrays.asList(l1, r1));

                l1 = l2;

                r1 = r2;

            }

        }

        anslist.add(Arrays.asList(l1, r1));

        return anslist;  

    }

The goal is to merge overlapping intervals from a list. To achieve this:

Sorting 📅:

• By sorting the intervals based on their start times, you align overlapping intervals next to each other. This simplifies the merging process because you only need to compare adjacent intervals.

Merging 🔗:

• Once sorted, iterate through the intervals and merge any that overlap. If an interval overlaps with the current interval being considered, extend the end of the current interval. If it doesn’t overlap, finalize the current interval and start a new one.

Sort Intervals 📊:

• Sort the intervals by their start time. This way, if intervals overlap, they will be next to each other in the sorted list.

Initialize Merging Process 🔄:

• Start with the first interval and initialize a list to store the merged intervals.

Iterate and Merge 🔗:

• Traverse through the sorted list of intervals.
• Compare each interval with the current interval being processed:
  • If Overlapping: Extend the end of the current interval to cover the new interval.
  • If Not Overlapping: Finalize the current interval, add it to the result list, and start a new interval.

Convert to Result Format 🔢:

• Convert the list of merged intervals to a 2D array before returning it.

• Time Complexity: O(nlogn)
  • Sorting the intervals takes O(nlog⁡n)
  • Merging intervals takes O(n)
• Space Complexity: O(n)
  • Space is used to store the merged intervals in a list.

import java.util.*;

public class Solution {
    public static List< List< Integer > > mergeOverlappingIntervals(int [][]arr){
        // Write your code here.
        int n=arr.length;

        if(n==0)
        return new ArrayList<>();
        List<int[]>ans=new ArrayList<>();
        int [] currinter=arr[0];
        ans.add(currinter);

        for(int i=1;i<n;i++)
        {
            int currstart=currinter[0];
            int currend=currinter[1];
            int nextstart=arr[i][0];
            int nextend=arr[i][1];
            if(currend>=nextstart)
            {
                currinter[1]=Math.max(currend,nextend);

            }
            else{
                currinter=arr[i];
                ans.add(currinter);
            }

        }


            List<List<Integer>> result = new ArrayList<>();
        for (int[] interval : ans) {
            result.add(Arrays.asList(interval[0], interval[1]));
        }

       return result;


    }
}

#include<vector>

vector<vector<int>> mergeOverlappingIntervals(vector<vector<int>> &arr){
	// Write your code here.
	int n = arr.size(); 
    vector<vector<int>> ans;
    for (int i = 0; i < n; i++) { 
        if(ans.empty() || arr[i][0]>ans.back()[1]) ans.push_back(arr[i]);
        else ans.back()[1]=max(ans.back()[1],arr[i][1]);
    }
    return ans;
}

#include<vector>

vector<vector<int>> mergeOverlappingIntervals(vector<vector<int>> &arr){

    int n = arr.size();

    sort(arr.begin(), arr.end());

    vector<vector<int>> ans;

    for(int i = 0; i < n ; i++){

          if (ans.empty() || arr[i][0] > ans.back()[1]) {

            ans.push_back(arr[i]);

          }

          else {

              ans.back()[1] = max(ans.back()[1] , arr[i][1] );

          }

        }

        return ans;

}

#  In this Code we will enter the first pair of sub-intervals in the ans vector. Then compare the next pair whether it is overlapping or not . 

To compare this , if the first unit of the pair is greater than the last unit of the pair that is in the ans vector , then it will surely be our new answer . So we have to add this in ans Vector.

But if the first unit of the pair is lesser than or equal to the last unit of the pair in the ans vector , then it surely be a part of the Overlapping , We have merge it with the existing overlapping , and change its last value to the maximum of two pairs.

vector<vector<int>> mergeOverlappingIntervals(vector<vector<int>> &arr){

    int n = arr.size();

    sort(arr.begin(),arr.end());

    vector<vector<int>> ans;

    for(int i = 0 ; i<n ; i++){

        if(ans.empty() || arr[i][0] > ans.back()[1]){

            ans.push_back(arr[i]);

        }

        else{

            ans.back()[1] = max(ans.back()[1], arr[i][1]);

        }

    }

    return ans;

}

steps to solve the current problem

Sorting:- The intervals are first sorted by their starting times.

create a vector array.

use a for loop… start with int i =0 to n.

taking two condition 

1. when  the vector array is empty or new subarray has to be taken .
2. when we have a subset and which has to be extended the overlapping..

lastly return the ans.

code given below….

#include <bits/stdc++.h>

#include<vector>

vector<vector<int>> mergeOverlappingIntervals(vector<vector<int>> &arr){

    vector<vector<int>>ans;

    sort(arr.begin(),arr.end());

    for(int i = 0; i<arr.size();i++){

        if(ans.empty() || arr[i][0]>ans.back()[1]){

            ans.push_back(arr[i]);

        }else{

            ans.back()[1] = max(arr[i][1],ans.back()[1]);

        }

    }

    return ans;

}

#include<vector>

vector<vector<int>> mergeOverlappingIntervals(vector<vector<int>> &arr){

    vector<vector<int>> ans;

    int n=arr.size();

    for(int i=0;i<n;i++){

        int start=arr[i][0]; //take start as the current element

        int end=arr[i][1]; //take end of the current element

        if(!ans.empty() and end<=ans.back()[1]){ //if the current interval already lying in the interval answered before

            continue;

        }

        for(int j=i+1;j<n;j++){ //for the ith element check from the 2nd element from it

            if(arr[j][0]<=end){ //in the next element from the current element ,cause j is i+1,if the start of the jth element is <= current's end 

                end=max(end,arr[j][1]); // then we need to get the greater end interval 

            }else{

                break; 

            }

        }

        ans.push_back({start,end});

    }

    return ans;

}