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++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Function to find the minimum number// of required groupsint minGroups(vector<vector<int> >& intervals){ // Initialise a map to keep the // intervals in the sorted ordered // based on start ranges map<int, int> mp; // Iterate over the each range of // ranges[] Increment the occurrence // of interval in map for (auto& i : intervals) { mp[i[0]]++; mp[i[1] + 1]--; } // Initialise a variable result to // represents the maximum number of // intervals that overlap. Initialise // a variable sum to represents the // number of intervals that overlap // at a particular time int result = 0, sum = 0; // Iterate over the map and calculate // the prefix sum of occurrence of // interval for (auto& it : mp) { // Maximise the result with maximum // number of intervals that overlap // at a particular time result = max(result, sum += it.second); } // Return the result return result;}// Driver code.int main(){ vector<vector<int> > ranges = { { 5, 10 }, { 6, 8 }, { 1, 5 }, { 2, 3 }, { 1, 10 } }; // Function Call cout << minGroups(ranges); return 0;} |
Java
// Java code to implement the approachimport java.io.*;import java.util.*;class GFG { // Function to find the minimum number // of required groups static int minGroups(int[][] intervals) { // Initialise a map to keep the // intervals in the sorted ordered // based on start ranges HashMap<Integer, Integer> mp = new HashMap<>(); // Iterate over the each range of // ranges[] Increment the occurrence // of interval in map for (int i = 0; i < 5; i++) { int a = intervals[i][0]; int b = intervals[i][1] + 1; if (mp.containsKey(a)) { var val = mp.get(a); mp.remove(a); mp.put(a, val + 1); } else mp.put(a, 1); if (mp.containsKey(b)) { var val = mp.get(b); mp.remove(b); mp.put(b, val - 1); } else mp.put(b, -1); } // Initialise a variable result to // represents the maximum number of // intervals that overlap. Initialise // a variable sum to represents the // number of intervals that overlap // at a particular time int result = 0, sum = 0; // Iterate over the map and calculate // the prefix sum of occurrence of // interval for (Integer it : mp.values()) { // Maximise the result with maximum // number of intervals that overlap // at a particular time result = Math.max(result, sum); sum += it; } // Return the result return result; } public static void main(String[] args) { int[][] ranges = { { 5, 10 }, { 6, 8 }, { 1, 5 }, { 2, 3 }, { 1, 10 } }; // Function call System.out.print(minGroups(ranges)); }}// This code is contributed by lokesh. |
Python3
# Python code to implement the approach# Function to find the minimum number# of required groupsdef minGroups(intervals): # Initialise a map to keep the # intervals in the sorted ordered # based on start ranges mp=[0]*10001 # Iterate over the each range of # ranges[] Increment the occurrence # of interval in map for i in range(len(intervals)): mp[intervals[i][0]]=mp[intervals[i][0]]+1 mp[intervals[i][1]+1]=mp[intervals[i][1]+1]-1 # Initialise a variable result to # represents the maximum number of # intervals that overlap. Initialise # a variable sum to represents the # number of intervals that overlap # at a particular time result, sum = 0, 0 # Iterate over the map and calculate # the prefix sum of occurrence of # interval for it in range(len(mp)): # Maximise the result with maximum # number of intervals that overlap # at a particular time sum = sum + mp[it] result = max(result, sum) # Return the result return result# Driver coderanges = [[5, 10],[6, 8],[1, 5],[2, 3],[1, 10]]# Function Callprint(minGroups(ranges))# This code is contributed by Pushpesh Raj. |
C#
using System;using System.Collections.Generic;class GFG { // Function to find the minimum number // of required groups static int minGroups(int[, ] intervals, int n) { // Initialise a map to keep the // intervals in the sorted ordered // based on start ranges SortedDictionary<int, int> mp = new SortedDictionary<int, int>(); // Iterate over the each range of // ranges[] Increment the occurrence // of interval in map for (int i = 0; i < n; i++) { int a = intervals[i, 0]; int b = intervals[i, 1] + 1; if (mp.ContainsKey(a)) { var val = mp[a]; mp.Remove(a); mp.Add(a, val + 1); } else mp.Add(a, 1); if (mp.ContainsKey(b)) { var val = mp[b]; mp.Remove(b); mp.Add(b, val - 1); } else mp.Add(b, -1); } // Initialise a variable result to // represents the maximum number of // intervals that overlap. Initialise // a variable sum to represents the // number of intervals that overlap // at a particular time int result = 0, sum = 0; // Iterate over the map and calculate // the prefix sum of occurrence of // interval foreach(KeyValuePair<int, int> it in mp) { // Maximise the result with maximum // number of intervals that overlap // at a particular time result = Math.Max(result, sum); sum += it.Value; } // Return the result return result; } static void Main() { int[, ] ranges = { { 5, 10 }, { 6, 8 }, { 1, 5 }, { 2, 3 }, { 1, 10 } }; // Function Call Console.Write(minGroups(ranges, 5)); }}// This code is contributed by garg28harsh. |
Javascript
// JavaScript code for the above approach // Function to find the minimum number // of required groups function minGroups(intervals) { // Initialise a map to keep the // intervals in the sorted ordered // based on start ranges let mp = new Array(10001).fill(0); // Iterate over the each range of // ranges[] Increment the occurrence // of interval in map for (let i = 0; i < intervals.length; i++) { mp[intervals[i][0]]++; mp[intervals[i][1] + 1]--; } // Initialise a variable result to // represents the maximum number of // intervals that overlap. Initialise // a variable sum to represents the // number of intervals that overlap // at a particular time let result = 0, sum = 0; // Iterate over the map and calculate // the prefix sum of occurrence of // interval for (let it = 0; it < mp.length; it++) { // Maximise the result with maximum // number of intervals that overlap // at a particular time result = Math.max(result, sum += mp[it]); } // Return the result return result; } // Driver code. let ranges = [ [5, 10], [6, 8], [1, 5], [2, 3], [1, 10] ]; // Function Call console.log(minGroups(ranges));// This code is contributed by Potta Lokesh |
Output
3
Time Complexity: O(N)
Auxiliary Space: O(N)
Share your thoughts in the comments
