Number of ways to choose K intersecting line segments on X-axis

0 0 8 minutes read

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 ⁿC_k
We pre-calculate the inverse and factorial of required numbers to calculate ⁿC_k
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 ^pC_k-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 b
long 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 nCk
long 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 ways
void 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 inverse
void 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 code
int 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-axis
import 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-axis
 
import heapq as hq
 
mod = 1000000007
MAXN = 1001
factorial=[1]*MAXN; inverse=[1]*MAXN
 
# Function to find (a^b)%mod in log b
def 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 nCk
def 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 ways
def 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 inverse
def 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 code
if __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-axis
using 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

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 zambiatek!