Number of intersections between two ranges

0 0 6 minutes read

Given N ranges of type₁ ranges and M ranges of type₂.The task is to find the total number of intersections between all possible type₁ and type₂ range pairs. All start and end points of type₁ and type₂ ranges are given.
Examples:

Input : N = 2, M = 2
type1[ ] = { { 1, 3 }, { 5, 9 } }
type2[ ] = { { 2, 8 }, { 9, 12 } }
Output : 3
Range {2, 8} intersects with type₁ ranges {1, 3} and {5, 9}
Range {9, 12} intersects with {5, 9} only.
So the total number of intersections is 3.
Input : N = 3, M = 1
type1[ ] = { { 1, 8 }, { 5, 10 }, { 14, 28 }
type2[ ] = { { 2, 8 } }
Output : 2

Approach:

Idea is to use inclusion-exclusion method to determine the total number of intersections.
Total possible number of intersections are n * m. Now subtract those count of type₁ ranges which do not intersect with i^th type₂ range.
Those type₁ ranges will not intersect with i^th type₂ range which ends before starts of i^th type₂ range and starts after the end of i^th type₂ range.
This count can be determined by using binary search . The C++ inbuilt function upper_bound can be used directly.

Below is the implementation of above approach:

CPP

// C++ implementation of above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return total
// number of intersections
int FindIntersection(pair<int, int> type1[], int n,
                     pair<int, int> type2[], int m)
{
 
    // Maximum possible number
    // of intersections
    int ans = n * m;
 
    vector<int> start, end;
    for (int i = 0; i < n; i++) {
 
        // Store all starting
        // points of type1 ranges
        start.push_back(type1[i].first);
 
        // Store all endpoints
        // of type1 ranges
        end.push_back(type1[i].second);
    }
 
    sort(start.begin(), start.end());
    sort(end.begin(), end.end());
 
    for (int i = 0; i < m; i++) {
 
        // Starting point of type2 ranges
        int L = type2[i].first;
 
        // Ending point of type2 ranges
        int R = type2[i].second;
 
        // Subtract those ranges which
        // are starting after R
        ans -= (start.end() - 
        upper_bound(start.begin(), start.end(), R));
 
        // Subtract those ranges which
        // are ending before L
        ans -= 
        (upper_bound(end.begin(), end.end(), L - 1) 
        - end.begin());
    }
 
    return ans;
}
 
// Driver Code
int main()
{
 
    pair<int, int> type1[] =
    { { 1, 2 }, { 2, 3 }, { 4, 5 }, { 6, 7 } };
 
    pair<int, int> type2[] = 
    { { 1, 5 }, { 2, 3 }, { 4, 7 }, { 5, 7 } };
 
    int n = sizeof(type1) / (sizeof(type1[0]));
    int m = sizeof(type2) / sizeof(type2[0]);
 
    cout << FindIntersection(type1, n, type2, m);
 
    return 0;
}

Java

// Java implementation of above approach 
import java.io.*;
import java.util.*;
class GFG
{
    static int upperBound(ArrayList<Integer> a, int low, 
                          int high, int element) 
    {
    while (low < high)
    {
        int middle = low + (high - low) / 2;
        if (a.get(middle) > element)
        {
            high = middle;
        }
      else
      {
            low = middle + 1;
        }
    }
    return low;
    }
   
    // Function to return total 
    // number of intersections 
    static int FindIntersection(ArrayList<ArrayList<Integer>> type1,
                                int n, ArrayList<ArrayList<Integer>> type2, int m )
    {
       
        // Maximum possible number 
        // of intersections 
        int ans = n * m;
        ArrayList<Integer> start = new ArrayList<Integer>();
        ArrayList<Integer> end = new ArrayList<Integer>();
        for (int i = 0; i < n; i++)
        {
           
            // Store all starting 
            // points of type1 ranges 
            start.add(type1.get(i).get(0));
             
            // Store all endpoints 
            // of type1 ranges
            end.add(type1.get(i).get(1));
             
        }
        Collections.sort(start);
        Collections.sort(end);
         
        for (int i = 0; i < m; i++)
        {
           
            // Starting point of type2 ranges 
            int L = type2.get(i).get(0);
           
            // Ending point of type2 ranges 
            int R = type2.get(i).get(1);
             
            // Subtract those ranges which 
            // are starting after R 
            ans -= start.size() - upperBound(start, 0, start.size(), R);
             
            // Subtract those ranges which 
            // are ending before L 
            ans -= upperBound(end, 0, end.size() , L - 1);
             
        }
        return ans;
    }
   
    // Driver Code 
    public static void main (String[] args)
    {
        ArrayList<ArrayList<Integer>> type1 = new ArrayList<ArrayList<Integer>>();
        type1.add(new ArrayList<Integer>(Arrays.asList(1,2)));
        type1.add(new ArrayList<Integer>(Arrays.asList(2,3)));
        type1.add(new ArrayList<Integer>(Arrays.asList(4,5)));
        type1.add(new ArrayList<Integer>(Arrays.asList(6,7)));
         
        ArrayList<ArrayList<Integer>> type2 = new ArrayList<ArrayList<Integer>>();
        type2.add(new ArrayList<Integer>(Arrays.asList(1,5)));
        type2.add(new ArrayList<Integer>(Arrays.asList(2,3)));
        type2.add(new ArrayList<Integer>(Arrays.asList(4,7)));
        type2.add(new ArrayList<Integer>(Arrays.asList(5,7)));
         
        int n = type1.size();
        int m = type2.size();
         
        System.out.println(FindIntersection(type1, n, type2, m));
    }
}
 
// This code is contributed by avanitrachhadiya2155

Python3

# Python3 implementation of above approach
from bisect import bisect as upper_bound
 
# Function to return total
# number of intersections
def FindIntersection(type1, n, type2, m):
 
    # Maximum possible number
    # of intersections
    ans = n * m
 
    start = []
    end = []
    for i in range(n):
         
        # Store all starting
        # points of type1 ranges
        start.append(type1[i][0])
 
        # Store all endpoints
        # of type1 ranges
        end.append(type1[i][1])
 
    start = sorted(start)
    start = sorted(end)
 
    for i in range(m):
 
        # Starting point of type2 ranges
        L = type2[i][0]
 
        # Ending point of type2 ranges
        R = type2[i][1]
 
        # Subtract those ranges which
        # are starting after R
        ans -= (len(start)- upper_bound(start, R))
 
        # Subtract those ranges which
        # are ending before L
        ans -= (upper_bound(end, L - 1))
 
    return ans
 
# Driver Code
type1 = [ [ 1, 2 ], [ 2, 3 ], 
          [ 4, 5 ], [ 6, 7 ] ]
 
type2 = [ [ 1, 5 ], [ 2, 3 ], 
          [ 4, 7 ], [ 5, 7 ] ]
 
n = len(type1)
m = len(type2)
 
print(FindIntersection(type1, n, type2, m))
 
# This code is contributed by Mohit Kumar

C#

// C# implementation of above approach 
using System;
using System.Collections.Generic;
class GFG
{
  static int upperBound(List<int> a, int low, 
                        int high, int element) 
  {
    while (low < high)
    {
      int middle = low + (high - low) / 2;
      if (a[middle] > element)
      {
        high = middle;
      }
      else
      {
        low = middle + 1;
      }
    }
    return low;
  }
 
  // Function to return total 
  // number of intersections
  static int FindIntersection(List<List<int>> type1, int n, 
                              List<List<int>> type2, int m)
  {
 
    // Maximum possible number 
    // of intersections 
    int ans = n * m;
    List<int> start = new List<int>();
    List<int> end = new List<int>();
    for (int i = 0; i < n; i++)
    {
 
      // Store all starting 
      // points of type1 ranges 
      start.Add(type1[i][0]);
 
      // Store all endpoints 
      // of type1 ranges
      end.Add(type1[i][1]);
    }
    start.Sort();
    end.Sort();
 
    for (int i = 0; i < m; i++)
    {
 
      // Starting point of type2 ranges 
      int L = type2[i][0];
 
      // Ending point of type2 ranges 
      int R = type2[i][1];
 
      // Subtract those ranges which 
      // are starting after R 
      ans -= start.Count - upperBound(start, 0, start.Count, R);
 
      // Subtract those ranges which 
      // are ending before L 
      ans -= upperBound(end, 0, end.Count , L - 1);
    }
    return ans;
  }
 
  // Driver Code 
  static public void Main ()
  {
    List<List<int>> type1 = new List<List<int>>();
    type1.Add(new List<int>(){1,2});
    type1.Add(new List<int>(){2,3});
    type1.Add(new List<int>(){4,5});
    type1.Add(new List<int>(){6,7});
 
    List<List<int>> type2 = new List<List<int>>();
    type2.Add(new List<int>(){1,5});
    type2.Add(new List<int>(){2,3});
    type2.Add(new List<int>(){4,7});
    type2.Add(new List<int>(){5,7});        
    int n = type1.Count;
    int m = type2.Count;
    Console.WriteLine(FindIntersection(type1, n, type2, m));        
  }
}
 
// This code is contributed by rag2127

Javascript

<script>
// Javascript implementation of above approach
 
function upperBound(a,low,high,element)
{
    while (low < high)
    {
        let middle = low + Math.floor((high - low) / 2);
        if (a[middle] > element)
        {
            high = middle;
        }
      else
      {
            low = middle + 1;
        }
    }
    return low;
}
 
// Function to return total
    // number of intersections
function FindIntersection(type1,n,type2,m)
{
    // Maximum possible number
        // of intersections
        let ans = n * m;
        let start = [];
        let end = [];
        for (let i = 0; i < n; i++)
        {
            
            // Store all starting
            // points of type1 ranges
            start.push(type1[i][0]);
              
            // Store all endpoints
            // of type1 ranges
            end.push(type1[i][1]);
              
        }
        start.sort(function(a,b){return a-b;});
        end.sort(function(a,b){return a-b;});
          
        for (let i = 0; i < m; i++)
        {
            
            // Starting point of type2 ranges
            let L = type2[i][0];
            
            // Ending point of type2 ranges
            let R = type2[i][1];
              
            // Subtract those ranges which
            // are starting after R
            ans -= start.length - upperBound(start, 0, start.length, R);
              
            // Subtract those ranges which
            // are ending before L
            ans -= upperBound(end, 0, end.length , L - 1);
              
        }
        return ans;
}
 
 // Driver Code
let type1 = [ [ 1, 2 ], [ 2, 3 ],
          [ 4, 5 ], [ 6, 7 ] ];
           
let type2 = [ [ 1, 5 ], [ 2, 3 ],
          [ 4, 7 ], [ 5, 7 ] ];
 
let n = type1.length;
let m = type2.length;
 
document.write(FindIntersection(type1, n, type2, m));
 
// This code is contributed by patel2127
</script>

Output:

Time Complexity: O(M*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 zambiatek!