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 nCrint 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 Codeint 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 approachimport 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 nCrstatic 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 Codepublic 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 nCrdef 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 Codeif __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 nCrfunction 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 Inputlet N = 7, K = 3;let L = [1, 3, 4, 6, 1, 5, 8];let R = [7, 8, 5, 7, 3, 10, 9];// Function Calldocument.write(NumberOfWaysToChooseKRanges(L, R, N, K));</script> |
C#
// C# program for the above approachusing System;using System.Collections.Generic;// Driver Codeclass 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)); }} |
Output
9
Time Complexity: O(N*log(N))
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
