Select Page

# 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 ``using` `namespace` `std;`` ` `int` `minGroups(vector >& intervals)``{``    ``    ``    ``    ``map<``int``, ``int``> mp;`` ` `    ``    ``    ``    ``for` `(``auto``& i : intervals) {``        ``mp[i]++;``        ``mp[i + 1]--;``    ``}`` ` `    ``    ``    ``    ``    ``    ``    ``int` `result = 0, sum = 0;`` ` `    ``    ``    ``    ``for` `(``auto``& it : mp) {`` ` `        ``        ``        ``        ``result = max(result, sum += it.second);``    ``}`` ` `    ``    ``return` `result;``}`` ` `int` `main()``{``    ``vector > 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