Given an array arr[] of line segments on the x-axis and an integer K, the task is to calculate the number of ways to choose the K line-segments such that they do intersect at any point. Since the answer can be large, print it to modulo 10^9+7.
Examples:
Input: arr[] = [[1, 3], [4, 5], [5, 7]], K = 2
Output: 2
Explanation:
The first way to choose [1, 3], [4, 5] and the second way is [1, 3], [5, 7].Since Intersection of [4, 5], [5, 7] is not zero and hence cannot be included in answer.Input: [[3, 7], [1, 4], [6, 9], [8, 13], [9, 11]], K = 1
Output: 0
Explanation:
Since we are only looking for single line segment, but for every single line segment Intersection is always non empty.
Approach:
To solve the problem mentioned above we will try to find out the number of odd cases means those cases whose intersection is non-empty. So clearly our answer will be Total Case – Odd Case.
To compute the total number of cases, the below approach is followed:
- Total cases that are possible are “n choose k” or nCk
- We pre-calculate the inverse and factorial of required numbers to calculate nCk
- in O(1) time
- The K line-segment intersect as if min(R1, R2, .., R{k-1}) >= Li where line-segment [Li, Ri] is under consideration. Maintain a multiset, to maintain order. Firstly, sort the segments in increasing order of Li . If Li are same then the segment with smaller Ri comes first.
For every line-segment [Li, Ri], the approach below is followed to find the number of odd cases.
- While multiset is not empty, and the lines don’t intersect then delete the line with smallest Ri from multiset and check again.
- Number of violating ways using this segment [Li, Ri] are pCk-1
- where p = size_of_multiset.
- Insert end-point of this line-segment in the multiset.
Below is the implementation of the above approach:
C++
// C++ program to find Number of ways// to choose K intersecting// line segments on X-axis#include <bits/stdc++.h>using namespace std;const long long mod = 1000000007;const int MAXN = 1001;long long factorial[MAXN], inverse[MAXN];// Function to find (a^b)%mod in log blong long power(long long a, long long b){ long long res = 1; // Till power becomes 0 while (b > 0) { // If power is odd if (b % 2 == 1) { res = (res * a) % mod; } // Multiply base a = (a * a) % mod; // Divide power by 1 b >>= 1; } return res;}// Function to find nCklong long nCk(int n, int k){ // Base case if (k < 0 || k > n) { return 0; } // Apply formula to find nCk long long ans = factorial[n]; ans = (ans * inverse[n - k]) % mod; ans = (ans * inverse[k]) % mod; return ans;}// Function to find the number of waysvoid numberOfWays(vector<pair<int, int> > lines, int K, int N){ // sort the given lines sort(lines.begin(), lines.end()); // Find the number of total case long long total_case = nCk(N, K); // Declare a multiset multiset<int> m; // loop till N for (int i = 0; i < N; i++) { // Check if smallest element is // smaller than lines[i] while (!m.empty() && (*m.begin() < lines[i].first)) { // Erase first element m.erase(m.begin()); } // Exclude the odd cases total_case -= nCk(m.size(), K - 1); // Modulus operation total_case += mod; total_case %= mod; // Insert into multiset m.insert(lines[i].second); } cout << total_case << endl;}// Function to precompute// factorial and inversevoid preCompute(){ long long fact = 1; factorial[0] = 1; inverse[0] = 1; // Pre-compute factorial and inverse for (int i = 1; i < MAXN; i++) { fact = (fact * i) % mod; factorial[i] = fact; inverse[i] = power(factorial[i], mod - 2); }}// Driver codeint main(){ int N = 3, K = 2; vector<pair<int, int> > lines; // Function to pre-compute // factorial and inverse preCompute(); lines.push_back({ 1, 3 }); lines.push_back({ 4, 5 }); lines.push_back({ 5, 7 }); numberOfWays(lines, K, N); return 0;} |
Java
// Java program to find Number of ways// to choose K intersecting line// segments on X-axisimport java.util.*;import java.lang.*;class GFG { static long mod = 1000000007; static int MAXN = 1001; static long factorial[] = new long[MAXN], inverse[] = new long[MAXN]; // Function to find (a^b)%mod in log b static long power(long a, long b) { long res = 1; // Till power becomes 0 while (b > 0) { // If power is odd if (b % 2 == 1) { res = (res * a) % mod; } // Multiply base a = (a * a) % mod; // Divide power by 1 b >>= 1; } return res; } // Function to find nCk static long nCk(int n, int k) { // Base case if (k < 0 || k > n) { return 0; } // Apply formula to find nCk long ans = factorial[n]; ans = (ans * inverse[n - k]) % mod; ans = (ans * inverse[k]) % mod; return ans; } // Function to find the number of ways static void numberOfWays(ArrayList<int[]> lines, int K, int N) { // sort the given lines Collections.sort(lines, (a, b) -> a[0] - b[0]); // Find the number of total case long total_case = nCk(N, K); // Declare a multiset PriorityQueue<Integer> m = new PriorityQueue<>(); // Loop till N for (int i = 0; i < N; i++) { // Check if smallest element is // smaller than lines[i] while (!m.isEmpty() && (m.peek() < lines.get(i)[0])) { // Erase first element m.poll(); } // Exclude the odd cases total_case -= nCk(m.size(), K - 1); // Modulus operation total_case += mod; total_case %= mod; // Insert into multiset m.add(lines.get(i)[1]); } System.out.println(total_case); } // Function to precompute // factorial and inverse static void preCompute() { long fact = 1; factorial[0] = 1; inverse[0] = 1; // Pre-compute factorial and inverse for (int i = 1; i < MAXN; i++) { fact = (fact * i) % mod; factorial[i] = fact; inverse[i] = power(factorial[i], mod - 2); } } // Driver code public static void main(String[] args) { int N = 3, K = 2; ArrayList<int[]> lines = new ArrayList<>(); // Function to pre-compute // factorial and inverse preCompute(); lines.add(new int[] { 1, 3 }); lines.add(new int[] { 4, 5 }); lines.add(new int[] { 5, 7 }); numberOfWays(lines, K, N); }}// This code is contributed by offbeat |
Python3
# Python3 program to find Number of ways# to choose K ersecting# line segments on X-axisimport heapq as hqmod = 1000000007MAXN = 1001factorial=[1]*MAXN; inverse=[1]*MAXN# Function to find (a^b)%mod in log bdef power(a, b): res = 1 # Till power becomes 0 while (b > 0) : # If power is odd if (b % 2 == 1) : res = (res * a) % mod # Multiply base a = (a * a) % mod # Divide power by 1 b >>= 1 return res# Function to find nCkdef nCk(n, k): # Base case if (k < 0 or k > n) : return 0 # Apply formula to find nCk ans = factorial[n] ans = (ans * inverse[n - k]) % mod ans = (ans * inverse[k]) % mod return ans# Function to find the number of waysdef numberOfWays(lines, K, N): # sort the given lines lines.sort() # Find the number of total case total_case = nCk(N, K) # Declare a heap m=[] # loop till N for i in range(N): # Check if smallest element is # smaller than lines[i] while (m and m[0] < lines[i][0]): # Erase first element hq.heappop(m) # Exclude the odd cases total_case -= nCk(len(m), K - 1) # Modulus operation total_case += mod total_case %= mod # Insert into heap hq.heappush(m,lines[i][1]) print(total_case)# Function to precompute# factorial and inversedef preCompute(): global factorial fact = 1 factorial[0] = 1 inverse[0] = 1 # Pre-compute factorial and inverse for i in range(1,MAXN) : fact = (fact * i) % mod factorial[i] = fact inverse[i] = power(factorial[i], mod - 2) # Driver codeif __name__ == '__main__': N = 3; K = 2 lines=[] # Function to pre-compute # factorial and inverse preCompute() lines.append((1, 3)) lines.append((4, 5)) lines.append((5, 7)) numberOfWays(lines, K, N) |
C#
// C// program to find Number of ways// to choose K ersecting// line segments on X-axisusing System;using System.Collections.Generic;namespace ConsoleApp1{ class Program { const int mod = 1000000007; const int MAXN = 1001; static long[] factorial = new long[MAXN]; static long[] inverse = new long[MAXN]; // Driver code static void Main(string[] args) { int N = 3, K = 2; List<(int, int)> lines = new List<(int, int)>(); // Function to pre-compute // factorial and inverse PreCompute(); lines.Add((1, 3)); lines.Add((4, 5)); lines.Add((5, 7)); NumberOfWays(lines, K, N); } // Function to precompute // factorial and inverse static void PreCompute() { long fact = 1; factorial[0] = 1; inverse[0] = 1; // Pre-compute factorial and inverse for (int i = 1; i < MAXN; i++) { fact = (fact * i) % mod; factorial[i] = fact; inverse[i] = Power(factorial[i], mod - 2); } } // Function to find (a^b)%mod in log b static long Power(long a, int b) { long res = 1; // Till power becomes 0 while (b > 0) { // If power is odd if (b % 2 == 1) { res = (res * a) % mod; } // Multiply base a = (a * a) % mod; // Divide power by 1 b >>= 1; } return res; } // Function to find nCk static long NCk(int n, int k) { // Base case if (k < 0 || k > n) { return 0; } // Apply formula to find nCk long ans = factorial[n]; ans = (ans * inverse[n - k]) % mod; ans = (ans * inverse[k]) % mod; return ans; } // Function to find the number of ways static void NumberOfWays(List<(int, int)> lines, int K, int N) { // sort the given lines lines.Sort(); // Find the number of total case long total_case = NCk(N, K); // Declare a heap List<int> m = new List<int>(); // loop till N for (int i = 0; i < N; i++) { // Check if smallest element is // smaller than lines[i] while (m.Count > 0 && m[0] < lines[i].Item1) { // Erase first element m.RemoveAt(0); } // Exclude the odd cases total_case -= NCk(m.Count, K - 1); // Modulus operation total_case += mod; total_case %= mod; // Insert into heap m.Add(lines[i].Item2); } Console.WriteLine(total_case); } }}// this code is contributed by Shivhack999 |
Output
2
Time Complexity: O(MAXN * log(MAXN) + N * log(N)).
Auxiliary Space: O(MAXN + 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!
