Problem Statement

Given a set of N intervals, the task is to find the maximal set of mutually disjoint intervals. Two intervals [i, j] & [k, l] are said to be disjoint if they do not have any point in common.

Examples:

Input: intervals[][] = {{1, 4}, {2, 3}, {4, 6}, {8, 9}} Output: [2, 3] [4, 6] [8, 9] Intervals sorted w.r.t. end points = {{2, 3}, {1, 4}, {4, 6}, {8, 9}} Intervals [2, 3] and [1, 4] overlap. We must include [2, 3] because if [1, 4] is included then we cannot include [4, 6].Input: intervals[][] = {{1, 9}, {2, 3}, {5, 7}} Output: [2, 3] [5, 7]

Problem Link

Disjoint Intervals - InterviewBit

Reference Link

Maximal Disjoint Intervals - GeeksforGeeks

Code

static bool compare(vector<int> &v1, vector<int> &v2)
{
    return (v1[1]<v2[1]);
}
 
int Solution::solve(vector<vector<int> > &A) {
 
    int n = A.size();
 
    if(n<=1)
    return n;
    
    // Sort the list of intervals wrt to end time 
    sort(A.begin(),A.end(),compare);
    
    int res = 1;

    // End point of first interval 
    int r1 = A[0][1];
    
 
    for(int i=1;i<n;i++)
    {
        int l1 = A[i][0];
        int r2 = A[i][1];
 
        // Check if given interval overlap with
        // previously included interval, if not
        // then include this interval and update
        // the end point of last added interval
				if(l1>r1)
        {
            res++;
            r1 = r2;
        }
 
    }
    return res;
 
    
    return 0;
}

Another way

#include <bits/stdc++.h>
using namespace std;

bool comp(const vector<int> &a, const vector<int> &b)
{
    return (a[1] < b[1]);
}

// Function to find maximal disjoint set
vector<vector<int>> getDisjoint(vector<vector<int>> &arr)
{

    // Sort the array of intervals
    // based on second element
    sort(arr.begin(), arr.end(), comp);

    // Stores the end point of the last
    // interval included in the maximal
    int end = -1;

    // Stores the maximal disjoint set
    vector<vector<int>> ans;

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

        if (arr[i][0] > end)
        {
            ans.push_back(arr[i]);
            end = arr[i][1];
        }
    }

    return ans;
}

// Driver code
int main()
{
    vector<vector<int>> arr = {{1, 4}, {2, 3}, {4, 6}, {8, 9}};
    vector<vector<int>> ans = getDisjoint(arr);
    for (int i = 0; i < ans.size(); i++)
    {
        cout << ans[i][0] << " " << ans[i][1] << endl;
    }
    return 0;
}