Minimize group such that no two range of same group intersect

Kashish Kumar
Published: November 9, 2022

Given an array ranges[] of size N (1 ≤ N ≤ 105), where ranges[i] = {starti, endi} represents the range between starti to endi (both inclusive). The task is to find the minimum number of groups that are needed such that each interval of ranges[] belongs to exactly one group and no two ranges[i] in the same group will intersect with each other.

Note: Two intervals intersect if at least one common number exists between them. For example, the intervals [2, 6] and [6, 7] intersect.

Examples:

Input: ranges[] = {{5, 10}, {6, 8}, {1, 5}, {2, 3}, {1, 10}}
Output: 3
Explanation: We can divide the range[] into the following groups:
Group 1: {1, 5}, {6, 8}.
Group 2: {2, 3}, {5, 10}.
Group 3: {1, 10}.

Input: ranges[] = {{1, 3], {5, 6}, {8, 10}, {11, 13}}
Output: 1

An approach using line sweep:

The idea is to keep track of maximum number of overlapping intervals at any time say N. So there should be N numbers of individual groups to avoid any intersection internally in group.

Follow the steps below to implement the above idea:

  • Initialize a map to keep the ranges in the sorted order based on the start range
  • Initialize a variable result to represent the maximum number of intervals that overlap.
  • Iterate over each range of ranges[]
    • Increment the occurrences of range in the map
  • Initialize a variable sum to represent the number of ranges that overlap at a particular time
  • Iterate over the map and calculate the prefix sum of occurrence of range
    • Maximize the result with the maximum number of intervals that overlap at a specific time
  • Return the result

Below is the implementation of the above approach:

C++

  

#include <bits/stdc++.h>

using namespace std;

  

int minGroups(vector<vector<int> >& intervals)

{

    

    

    

    map<int, int> mp;

  

    

    

    

    for (auto& i : intervals) {

        mp[i[0]]++;

        mp[i[1] + 1]--;

    }

  

    

    

    

    

    

    

    int result = 0, sum = 0;

  

    

    

    

    for (auto& it : mp) {

  

        

        

        

        result = max(result, sum += it.second);

    }

  

    

    return result;

}

  

int main()

{

    vector<vector<int> > ranges = {

        { 5, 10 }, { 6, 8 }, { 1, 5 }, { 2, 3 }, { 1, 10 }

    };

  

    

    cout << minGroups(ranges);

  

    return 0;

}

Time Complexity: O(N)
Auxiliary Space: O(N)

Source: www.geeksforgeeks.org