Count of ways to select exactly K non-disjoint ranges from given N ranges
Given two arrays L[] and R[] of size N, and an integer K, the task is to find the number of ways to select exact K disjoint ranges formed by taking elements present at the same index from the array L[] and R[].
Examples:
Input: N = 7, K = 3, L[] = {1, 3, 4, 6, 1, 5, 8}, R[] = {7, 8, 5, 7, 3, 10, 9}
Output: 9
Explanation:
The possible ways of selecting K ranges are:
- Select ranges {1, 7}, {3, 8}, and {4, 5}
- Select ranges {1, 7}, {3, 8}, and {6, 7}
- Select ranges {1, 7}, {3, 8}, and {1, 3}
- Select ranges {1, 7}, {3, 8}, and {5, 10}
- Select ranges {1, 7}, {4, 5}, and {5, 10}
- Select ranges {1, 7}, {6, 7}, and {5, 10}
- Select ranges {3, 8}, {4, 5}, and {5, 10}
- Select ranges {3, 8}, {6, 7}, and {5, 10}
- Select ranges {3, 8}, {5, 10}, and {8, 9}
Input: N = 2, K = 2, L[] = {100, 200}, R[] ={ 201, 300}
Output: 0
Naive Approach: The simplest approach to solve the problem is to select every possible distinct K pair and check if they are disjoint for every pair of all the ranges.
Time Complexity: O(N!)
Auxiliary Space: O(1)
Efficient Approach: The above approach can be optimized by checking for every range the number of non-disjoint ranges which can be used with the current range. Follow the steps below to optimize the above approach:
- Initialize a variable, say, cnt to count the number of non-disjoint ranges for every current range.
- Initialize a vector of pairs, say preprocessed to store all the left boundary as {L[i], 1} and the right boundary as {R[i]+1, -1} of a range.
- Iterate over the range [0, N], using the variable i, and perform the following steps:
- Push the pairs {L[i], 1} and {R[i]+1, -1} into the vector preprocessed.
- Sort the vector, preprocessed in non-decreasing order.
- Initialize variables, say ans and cnt as 0 to store the answer and to store the segment that intersects with the current range.
- Iterate over the vector preprocessed using the variable i and do the following:
- If the second element of the pair is 1 and cnt >= K-1, then increase the ans by cntCK-1 and update cnt to cnt+1.
- Otherwise, update the cnt as cnt+1.
- Finally, after completing the above steps, print the ans.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Utility function to calculate nCr int nCr( int n, int r, int * f) { return f[n] / f[r] * f[n - r]; } // Function to calculate number of ways // to choose K ranges such that no two of // them are disjoint. int NumberOfWaysToChooseKRanges( int L[], int R[], int N, int K) { // Stores the factorials int f[N + 1]; f[0] = 1; // Iterate over the range [1, N] for ( int i = 1; i <= N; i++) { f[i] = f[i - 1] * i; } // Preprocessing the ranges into // new vector vector<pair< int , int > > preprocessed; // Traverse the given ranges for ( int i = 0; i < N; i++) { preprocessed.push_back(make_pair(L[i], 1)); preprocessed.push_back(make_pair(R[i] + 1, -1)); } // Sorting the preprocessed vector sort(preprocessed.begin(), preprocessed.end()); // Stores the result int ans = 0; // Stores the count of non-disjoint ranges int Cnt = 0; // Traverse the preprocessed vector of pairs for ( int i = 0; i < preprocessed.size(); i++) { // If current point is a left boundary if (preprocessed[i].second == 1) { if (Cnt >= K - 1) { // Update the answer ans += nCr(Cnt, K - 1, f); } // Increment cnt by 1 Cnt++; } else { // Decrement cnt by 1 Cnt--; } } // Return the ans return ans; } // Driver Code int main() { // Given Input int N = 7, K = 3; int L[] = { 1, 3, 4, 6, 1, 5, 8 }; int R[] = { 7, 8, 5, 7, 3, 10, 9 }; // Function Call cout << NumberOfWaysToChooseKRanges(L, R, N, K); return 0; } |
Java
// Java program for the above approach import java.io.*; import java.util.*; class GFG { static class pair { int first, second; public pair( int first, int second) { this .first = first; this .second = second; } } // Utility function to calculate nCr static int nCr( int n, int r, int f[]) { return f[n] / f[r] * f[n - r]; } // Function to calculate number of ways // to choose K ranges such that no two of // them are disjoint. static int NumberOfWaysToChooseKRanges( int L[], int R[], int N, int K) { // Stores the factorials int f[] = new int [N + 1 ]; f[ 0 ] = 1 ; // Iterate over the range [1, N] for ( int i = 1 ; i <= N; i++) { f[i] = f[i - 1 ] * i; } // Preprocessing the ranges into // new vector Vector<pair > preprocessed = new Vector<pair >(); // Traverse the given ranges for ( int i = 0 ; i < N; i++) { preprocessed.add( new pair(L[i], 1 )); preprocessed.add( new pair(R[i] + 1 , - 1 )); } // Sorting the preprocessed vector Collections.sort(preprocessed, new Comparator<pair>() { @Override public int compare(pair p1, pair p2) { if (p1.first != p2.first) return (p1.first - p2.first); return p1.second - p2.second; } }); // Stores the result int ans = 0 ; // Stores the count of non-disjoint ranges int Cnt = 0 ; // Traverse the preprocessed vector of pairs for ( int i = 0 ; i < preprocessed.size(); i++) { // If current point is a left boundary if (preprocessed.elementAt(i).second == 1 ) { if (Cnt >= K - 1 ) { // Update the answer ans += nCr(Cnt, K - 1 , f); } // Increment cnt by 1 Cnt++; } else { // Decrement cnt by 1 Cnt--; } } // Return the ans return ans; } // Driver Code public static void main (String[] args) { // Given Input int N = 7 , K = 3 ; int L[] = { 1 , 3 , 4 , 6 , 1 , 5 , 8 }; int R[] = { 7 , 8 , 5 , 7 , 3 , 10 , 9 }; // Function Call System.out.println(NumberOfWaysToChooseKRanges(L, R, N, K)); } } // This code is contributed by Dharanendra L V. |
Python3
# Python3 program for the above approach # Utility function to calculate nCr def nCr(n, r, f): return f[n] / / f[r] * f[n - r] # Function to calculate number of ways # to choose K ranges such that no two of # them are disjoint. def NumberOfWaysToChooseKRanges(L, R, N, K): # Stores the factorials f = [ 0 for i in range (N + 1 )] f[ 0 ] = 1 # Iterate over the range [1, N] for i in range ( 1 , N + 1 , 1 ): f[i] = f[i - 1 ] * i # Preprocessing the ranges into # new vector preprocessed = [] # Traverse the given ranges for i in range (N): preprocessed.append([L[i], 1 ]) preprocessed.append([R[i] + 1 , - 1 ]) # Sorting the preprocessed vector preprocessed.sort() # Stores the result ans = 0 # Stores the count of non-disjoint ranges Cnt = 0 # Traverse the preprocessed vector of pairs for i in range ( len (preprocessed)): # If current point is a left boundary if (preprocessed[i][ 1 ] = = 1 ): if (Cnt > = K - 1 ): # Update the answer ans + = nCr(Cnt, K - 1 , f) # Increment cnt by 1 Cnt + = 1 else : # Decrement cnt by 1 Cnt - = 1 # Return the ans return ans # Driver Code if __name__ = = '__main__' : # Given Input N = 7 K = 3 L = [ 1 , 3 , 4 , 6 , 1 , 5 , 8 ] R = [ 7 , 8 , 5 , 7 , 3 , 10 , 9 ] # Function Call print (NumberOfWaysToChooseKRanges(L, R, N, K)) # This code is contributed by SURENDRA_GANGWAR |
Javascript
<script> // JavaScript program for the above approach // Utility function to calculate nCr function nCr(n, r, f) { return f[n] / f[r] * f[n - r]; } // Function to calculate number of ways // to choose K ranges such that no two of // them are disjoint. function NumberOfWaysToChooseKRanges(L, R, N, K) { // Stores the factorials let f = new Array(N + 1); f[0] = 1; // Iterate over the range [1, N] for (let i = 1; i <= N; i++) { f[i] = f[i - 1] * i; } // Preprocessing the ranges into // new vector let preprocessed = []; // Traverse the given ranges for (let i = 0; i < N; i++) { preprocessed.push([L[i], 1]); preprocessed.push([R[i] + 1, -1]); } // Sorting the preprocessed vector preprocessed.sort((a, b) => { if (a[0] != b[0]) return a[0] - b[0] return a[1] - b[1] }); // Stores the result let ans = 0; // Stores the count of non-disjoint ranges let Cnt = 0; // Traverse the preprocessed vector of pairs for (let i = 0; i < preprocessed.length; i++) { // If current point is a left boundary if (preprocessed[i][1] == 1) { console.log( "Hello babe" ) if (Cnt >= K - 1) { // Update the answer ans += nCr(Cnt, K - 1, f); } // Increment cnt by 1 Cnt++; } else { // Decrement cnt by 1 Cnt--; } } // Return the ans return ans; } // Driver Code // Given Input let N = 7, K = 3; let L = [1, 3, 4, 6, 1, 5, 8]; let R = [7, 8, 5, 7, 3, 10, 9]; // Function Call document.write(NumberOfWaysToChooseKRanges(L, R, N, K)); </script> |
C#
// C# program for the above approach using System; using System.Collections.Generic; // Driver Code class GFG { class pair : IComparable<pair> { public int first, second; // Constructor public pair( int first, int second) { this .first = first; this .second = second; } // Compare two pairs public int CompareTo(pair other) { if ( this .first != other.first) { return this .first - other.first; } return this .second - other.second; } } // Utility function to calculate nCr static int nCr( int n, int r, int [] f) { return f[n] / f[r] * f[n - r]; } // Function to calculate number of ways // to choose K ranges such that no two of // them are disjoint. static int NumberOfWaysToChooseKRanges( int [] L, int [] R, int N, int K) { // Stores the factorials int [] f = new int [N + 1]; f[0] = 1; // Iterate over the range [1, N] for ( int i = 1; i <= N; i++) { f[i] = f[i - 1] * i; } // Preprocessing the ranges into // new vector List<pair> preprocessed = new List<pair>(); // Traverse the given ranges for ( int i = 0; i < N; i++) { preprocessed.Add( new pair(L[i], 1)); preprocessed.Add( new pair(R[i] + 1, -1)); } // Sorting the preprocessed vector preprocessed.Sort(); // Stores the result int ans = 0; // Stores the count of non-disjoint ranges int Cnt = 0; for ( int i = 0; i < preprocessed.Count; i++) { // If current point is a left boundary if (preprocessed[i].second == 1) { if (Cnt >= K - 1) { // Update the answer ans += nCr(Cnt, K - 1, f); } // Increment cnt by 1 Cnt++; } else { // Decrement cnt by 1 Cnt--; } } // Return the ans return ans; } static void Main() { // Given Input int N = 7, K = 3; int [] L = { 1, 3, 4, 6, 1, 5, 8 }; int [] R = { 7, 8, 5, 7, 3, 10, 9 }; // Function Call Console.WriteLine(NumberOfWaysToChooseKRanges(L, R, N, K)); } } |
9
Time Complexity: O(N*log(N))
Auxiliary Space: O(N)