Maximum number of intervals that an interval can intersect

0 0 15 minutes read

Given an array arr[] consisting of N intervals of the form of [L, R], where L, R denotes the start and end positions of the interval, the task is to count the maximum number of intervals that an interval can intersect with each other.

Examples:

Input: arr[] = {{1, 2}, {3, 4}, {2, 5}}
Output: 3
Explanation: The required set of intervals are {1, 2}, {2, 5}, {3, 4} as {2, 5} intersect all other intervals.

Input: arr[] = {{1, 3}, {2, 4}, {3, 5}, {8, 11}}
Output: 3
Explanation: The required set of intervals are {1, 3}, {2, 4}, {3, 5} as {2, 4} intersect all other intervals.

Naive Approach: The simplest approach is to traverse the array and for each interval, count the number of intervals it intersects using a nested loop. After checking for each interval, print the maximum number of intervals that an interval can intersect.

Below is the implementation of the above approach:

C++

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to count the maximum number
// of intervals that an interval
// can intersect
void findMaxIntervals(
    vector<pair<int, int> > v, int n)
{
    // Store the required answer
    int maxi = 0;
 
    // Traverse all the intervals
    for (int i = 0; i < n; i++) {
 
        // Store the number of
        // intersecting intervals
        int c = n;
 
        // Iterate in the range[0, n-1]
        for (int j = 0; j < n; j++) {
 
            // Check if jth interval lies
            // outside the ith interval
            if (v[i].second < v[j].first
                || v[i].first > v[j].second) {
                c--;
            }
        }
 
        // Update the overall maximum
        maxi = max(c, maxi);
    }
 
    // Print the answer
    cout << maxi;
}
 
// Driver Code
int main()
{
    vector<pair<int, int> > arr
        = { { 1, 2 },
            { 3, 4 },
            { 2, 5 } };
    int N = arr.size();
 
    // Function Call
    findMaxIntervals(arr, N);
 
    return 0;
}

Java

// Java implementation of the approach
import java.util.*; 
class GFG
{
 
  static class Pair 
  {
    int first, second;
    public Pair(int first, int second)
    {
      this.first = first;
      this.second = second;
    }
  }
 
  // Function to count the maximum number
  // of intervals that an interval
  // can intersect
  static void findMaxIntervals(ArrayList<Pair> v, int n)
  {
 
    // Store the required answer
    int maxi = 0;
 
    // Traverse all the intervals
    for (int i = 0; i < n; i++)
    {
 
      // Store the number of
      // intersecting intervals
      int c = n;
 
      // Iterate in the range[0, n-1]
      for (int j = 0; j < n; j++) {
 
        // Check if jth interval lies
        // outside the ith interval
        if (v.get(i).second < v.get(j).first
            || v.get(i).first > v.get(j).second) {
          c--;
        }
      }
 
      // Update the overall maximum
      maxi = Math.max(c, maxi);
    }
 
    // Print the answer
    System.out.print(maxi);
  }
 
  // Driver code
  public static void main(String[] args)
  {
    ArrayList<Pair> arr = new ArrayList<>(); 
    arr.add(new Pair(1,2)); 
    arr.add(new Pair(3,4)); 
    arr.add(new Pair(2,5));
 
    int N = arr.size();
 
    // Function Call
    findMaxIntervals(arr, N);
  }
}
 
// This code is contributed by susmitakundugoaldnga.

Python3

# Python3 program for the above approach 
 
# Function to count the maximum number 
# of intervals that an interval 
# can intersect 
def findMaxIntervals(v, n) : 
    
    # Store the required answer 
    maxi = 0
     
    # Traverse all the intervals 
    for i in range(n) :
    
        # Store the number of 
        # intersecting intervals 
        c = n
    
        # Iterate in the range[0, n-1] 
        for j in range(n) :
    
            # Check if jth interval lies 
            # outside the ith interval 
            if (v[i][1] < v[j][0] or v[i][0] > v[j][1]) : 
             
                c -= 1
    
        # Update the overall maximum 
        maxi = max(c, maxi)
    
    # Print the answer 
    print(maxi)
     
    # Driver code
arr = []
arr.append((1,2))
arr.append((3,4))
arr.append((2,5))
N = len(arr) 
 
# Function Call 
findMaxIntervals(arr, N)
 
# This code is contributed by divyeshrabadiya07.

C#

// C# program for the above approach 
using System;
using System.Collections.Generic;
class GFG
{
     
    // Function to count the maximum number 
    // of intervals that an interval 
    // can intersect 
    static void findMaxIntervals(List<Tuple<int, int> > v, int n) 
    { 
       
        // Store the required answer 
        int maxi = 0; 
       
        // Traverse all the intervals 
        for (int i = 0; i < n; i++) 
        { 
       
            // Store the number of 
            // intersecting intervals 
            int c = n; 
       
            // Iterate in the range[0, n-1] 
            for (int j = 0; j < n; j++)
            { 
       
                // Check if jth interval lies 
                // outside the ith interval 
                if (v[i].Item2 < v[j].Item1 
                    || v[i].Item1 > v[j].Item2) 
                { 
                    c--; 
                } 
            } 
       
            // Update the overall maximum 
            maxi = Math.Max(c, maxi); 
        } 
       
        // Print the answer 
        Console.Write(maxi); 
    } 
 
  // Driver code
  static void Main() 
  {
    List<Tuple<int, int>> arr = new List<Tuple<int, int>>();
    arr.Add(new Tuple<int,int>(1,2));
    arr.Add(new Tuple<int,int>(3,4));
    arr.Add(new Tuple<int,int>(2,5));
    int N = arr.Count; 
   
    // Function Call 
    findMaxIntervals(arr, N);
  }
}
 
// This code is contributed by divyesh072019.

Javascript

<script>
 
// Javascript program for the above approach
 
// Function to count the maximum number
// of intervals that an interval
// can intersect
function findMaxIntervals( v, n)
{
    // Store the required answer
    var maxi = 0;
 
    // Traverse all the intervals
    for (var i = 0; i < n; i++) {
 
        // Store the number of
        // intersecting intervals
        var c = n;
 
        // Iterate in the range[0, n-1]
        for (var j = 0; j < n; j++) {
 
            // Check if jth interval lies
            // outside the ith interval
            if (v[i][1] < v[j][0]
                || v[i][0] > v[j][1]) {
                c--;
            }
        }
 
        // Update the overall maximum
        maxi = Math.max(c, maxi);
    }
 
    // Print the answer
    document.write( maxi);
}
 
// Driver Code
var arr
    = [ [ 1, 2 ],
        [ 3, 4 ],
        [ 2, 5 ] ];
var N = arr.length;
 
// Function Call
findMaxIntervals(arr, N);
 
</script>

Output

Time Complexity: O(N²)
Auxiliary Space: O(1)

Efficient Approach: The above approach can be optimized by instead of counting the number of intersections, count the number of intervals that do not intersect. The intervals that do not intersect with a particular interval can be divided into two disjoint categories: intervals that fall completely to the left or completely to the right. Using this idea, follow the steps below to solve the problem:

Create a hashmap, say M, to map the number of intervals that do not intersect with each interval.
Sort the intervals on the basis of their starting point.
Traverse the intervals using the variable i
- Initialize ans as -1 to store the index of the first interval lying completely to the right of i^th interval.
- Initialize low and high as (i + 1) and (N – 1) and perform a binary search as below:
  - Find the value of mid as (low + high)/2.
  - If the starting position of interval[mid] is greater than the ending position of interval[i], store the current index mid in ans and then check in the left half by updating high to (mid – 1).
  - Else check in the right half by updating low to (mid + 1).
- If the value of ans is not -1, add (N – ans) to M[interval[i]].
Now, sort the intervals on the basis of their ending point.
Again, traverse the intervals using the variable i and apply a similar approach as above to find the intervals lying completely to the left of the i^th interval.
After the loop, traverse the map M and store the minimum value in min.
Print the value of (N – min) as the result.

Below is the implementation of the above approach:

C++

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Comparator function to sort in
// increasing order of second
// values in each pair
bool compare(pair<int, int> f,
             pair<int, int> s)
{
    return f.second < s.second;
}
 
// Function to hash a pair
struct hash_pair {
    template <class T1, class T2>
    size_t operator()(
        const pair<T1, T2>& p) const
    {
        auto hash1 = hash<T1>{}(p.first);
        auto hash2 = hash<T2>{}(p.second);
        return hash1 ^ hash2;
    }
};
 
// Function to count maximum number
// of intervals that an interval
// can intersect
void findMaxIntervals(
    vector<pair<int, int> > v, int n)
{
 
    // Create a hashmap
    unordered_map<pair<int, int>,
                  int,
                  hash_pair>
        um;
 
    // Sort by starting position
    sort(v.begin(), v.end());
 
    // Traverse all the intervals
    for (int i = 0; i < n; i++) {
 
        // Initialize um[v[i]] as 0
        um[v[i]] = 0;
 
        // Store the starting and
        // ending point of the
        // ith interval
        int start = v[i].first;
        int end = v[i].second;
 
        // Set low and high
        int low = i + 1;
        int high = n - 1;
 
        // Store the required number
        // of intervals
        int ans = -1;
 
        // Apply binary search to find
        // the number of intervals
        // completely lying to the
        // right of the ith interval
        while (low <= high) {
 
            // Find the mid
            int mid = low + (high - low) / 2;
 
            // Condition for searching
            // in the first half
            if (v[mid].first > end) {
                ans = mid;
                high = mid - 1;
            }
 
            // Otherwise search in the
            // second half
            else {
                low = mid + 1;
            }
        }
 
        // Increment um[v[i]] by n-ans
        // if ans!=-1
        if (ans != -1)
            um[v[i]] = n - ans;
    }
 
    // Sort by ending position
    sort(v.begin(), v.end(), compare);
 
    // Traverse all the intervals
    for (int i = 0; i < n; i++) {
 
        // Store the starting and
        // ending point of the
        // ith interval
        int start = v[i].first;
        int end = v[i].second;
 
        // Set low and high
        int low = 0;
        int high = i - 1;
 
        // Store the required number
        // of intervals
        int ans = -1;
 
        // Apply binary search to
        // find the number of intervals
        // completely lying to the
        // left of the ith interval
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (v[mid].second < start) {
                ans = mid;
                low = mid + 1;
            }
            else {
                high = mid - 1;
            }
        }
 
        // Increment um[v[i]] by ans+1
        // if ans!=-1
        if (ans != -1)
            um[v[i]] += (ans + 1);
    }
 
    // Store the answer
    int res = 0;
 
    // Traverse the map
    for (auto it = um.begin();
         it != um.end(); it++) {
 
        // Update the overall answer
        res = max(res, n - it->second);
    }
 
    // Print the answer
    cout << res;
}
 
// Driver Code
int main()
{
    vector<pair<int, int> > arr
        = { { 1, 2 },
            { 3, 4 },
            { 2, 5 } };
 
    int N = arr.size();
 
    // Function Call
    findMaxIntervals(arr, N);
 
    return 0;
}

Java

// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
class GFG 
{
 
  // Pair class to store in the um as a key
  // with hashcode and equals
  static class Pair
  {
 
    int first;
    int second;
    public Pair(int first, int second)
    {
      this.first = first;
      this.second = second;
    }
 
    @Override public int hashCode()
    {
      final int prime = 31;
      int result = 1;
      result = prime * result + first;
      result = prime * result + second;
      return result;
    }
 
    @Override public boolean equals(Object obj)
    {
      if (this == obj)
        return true;
      if (obj == null)
        return false;
      if (getClass() != obj.getClass())
        return false;
      Pair other = (Pair)obj;
      if (first != other.first)
        return false;
      if (second != other.second)
        return false;
      return true;
    }
  }
 
  // Function to count maximum number
  // of intervals that an interval
  // can intersect
  static void findMaxIntervals(ArrayList<Pair> v, int n)
  {
 
    // Create a hashmap
    HashMap<Pair, Integer> um = new HashMap<>();
 
    // Sort by starting position
    Collections.sort(v, (x, y) -> x.first - y.first);
 
    // Traverse all the intervals
    for (int i = 0; i < n; i++) {
 
      // Initialize um for v[i] as 0
      um.put(v.get(i), 0);
 
      // Store the starting and
      // ending point of the
      // ith interval
      int start = v.get(i).first;
      int end = v.get(i).second;
 
      // Set low and high
      int low = i + 1;
      int high = n - 1;
 
      // Store the required number
      // of intervals
      int ans = -1;
 
      // Apply binary search to find
      // the number of intervals
      // completely lying to the
      // right of the ith interval
      while (low <= high) {
 
        // Find the mid
        int mid = low + (high - low) / 2;
 
        // Condition for searching
        // in the first half
        if (v.get(mid).first > end) {
          ans = mid;
          high = mid - 1;
        }
 
        // Otherwise search in the
        // second half
        else {
          low = mid + 1;
        }
      }
 
      // Increment um for v[i] by n-ans
      // if ans!=-1
      if (ans != -1)
        um.put(v.get(i), n - ans);
    }
 
    // Sort by ending position
    Collections.sort(v, (x, y) -> x.second - y.second);
 
    // Traverse all the intervals
    for (int i = 0; i < n; i++) {
 
      // Store the starting and
      // ending point of the
      // ith interval
      int start = v.get(i).first;
      int end = v.get(i).second;
 
      // Set low and high
      int low = 0;
      int high = i - 1;
 
      // Store the required number
      // of intervals
      int ans = -1;
 
      // Apply binary search to
      // find the number of intervals
      // completely lying to the
      // left of the ith interval
      while (low <= high) {
        int mid = low + (high - low) / 2;
        if (v.get(mid).second < start) {
          ans = mid;
          low = mid + 1;
        }
        else {
          high = mid - 1;
        }
      }
 
      // Increment um for v[i] by ans+1
      // if ans!=-1
      if (ans != -1)
        um.put(v.get(i),
               um.get(v.get(i)) + (ans + 1));
    }
 
    // Store the answer
    int res = 0;
 
    // Traverse the map
    for (int second : um.values()) {
 
      // Update the overall answer
      res = Math.max(res, n - second);
    }
 
    // Print the answer
    System.out.println(res);
  }
 
  // Driver Code
  public static void main(String[] args)
  {
 
    ArrayList<Pair> arr = new ArrayList<>();
    arr.add(new Pair(1, 2));
    arr.add(new Pair(3, 4));
    arr.add(new Pair(2, 5));
 
    int N = arr.size();
 
    // Function Call
    findMaxIntervals(arr, N);
  }
}
 
// This code is contributed by Kingash.

Python3

from typing import List, Tuple
from collections import defaultdict
 
# Function to find the maximum number of intervals that an interval can intersect
def findMaxIntervals(v: List[Tuple[int,int]]) -> None:
    # Sort the intervals by their starting position
    v.sort()
    n = len(v)
    # Use a dictionary to store the number of intervals that can intersect with each interval
    um = defaultdict(int)
 
    # Iterate through all the intervals
    for i in range(n):
        # Store the starting and ending point of the current interval
        start = v[i][0]
        end = v[i][1]
 
        low = i + 1
        high = n - 1
        ans = -1
        # Use binary search to find the number of intervals completely lying to the right of the current interval
        while low <= high:
            mid = low + (high - low) // 2
            if v[mid][0] > end:
                ans = mid
                high = mid - 1
            else:
                low = mid + 1
 
        # Increment the number of intersecting intervals in the dictionary
        if ans != -1:
            um[v[i]] = n - ans
 
    # Sort the intervals by their ending position
    v.sort(key=lambda x: (x[1], x[0]))
 
    # Iterate through all the intervals
    for i in range(n):
        # Store the starting and ending point of the current interval
        start = v[i][0]
        end = v[i][1]
 
        low = 0
        high = i - 1
        ans = -1
        # Use binary search to find the number of intervals completely lying to the left of the current interval
        while low <= high:
            mid = low + (high - low) // 2
            if v[mid][1] < start:
                ans = mid
                low = mid + 1
            else:
                high = mid - 1
 
        # Increment the number of intersecting intervals in the dictionary
        if ans != -1:
            um[v[i]] += (ans + 1)
 
    # Find the interval with the maximum number of non-intersecting intervals
    res = 0
    for key, val in sorted(um.items()):
        res = max(res, n - val + 1)
    print(res)
     
 
arr = [(1, 2), (3, 4), (2, 5)]
findMaxIntervals(arr)

C#

// C# program to implement the approach
 
using System;
using System.Collections.Generic;
using System.Linq;
 
class GFG {
    // Pair class to store in the um as a key
    // with hashcode and equals
    private class Pair {
        public int first
        {
            get;
            set;
        }
        public int second
        {
            get;
            set;
        }
 
        public Pair(int first, int second)
        {
            this.first = first;
            this.second = second;
        }
 
        public override int GetHashCode()
        {
            int prime = 31;
            int result = 1;
            result = prime * result + first;
            result = prime * result + second;
            return result;
        }
 
        public override bool Equals(object obj)
        {
            if (this == obj)
                return true;
            if (obj == null)
                return false;
            if (GetType() != obj.GetType())
                return false;
            Pair other = (Pair)obj;
            if (first != other.first)
                return false;
            if (second != other.second)
                return false;
            return true;
        }
    }
 
    // Function to count maximum number
    // of intervals that an interval
    // can intersect
    static void FindMaxIntervals(List<Pair> v, int n)
    {
        // Create a hashmap
        Dictionary<Pair, int> um
            = new Dictionary<Pair, int>();
 
        // Sort by starting position
        v.Sort((x, y) => x.first - y.first);
 
        // Traverse all the intervals
        for (int i = 0; i < n; i++) {
            // Initialize um for v[i] as 0
            um.Add(v[i], 0);
 
            // Store the starting and
            // ending point of the
            // ith interval
            int start = v[i].first;
            int end = v[i].second;
 
            // Set low and high
            int low = i + 1;
            int high = n - 1;
 
            // Store the required number
            // of intervals
            int ans = -1;
 
            // Apply binary search to find
            // the number of intervals
            // completely lying to the
            // right of the ith interval
            while (low <= high) {
                // Find the mid
                int mid = low + (high - low) / 2;
 
                // Condition for searching
                // in the first half
                if (v[mid].first > end) {
                    ans = mid;
                    high = mid - 1;
                }
 
                // Otherwise search in the
                // second half
                else {
                    low = mid + 1;
                }
            }
 
            // Increment um for v[i] by n-ans
            // if ans!=-1
            if (ans != -1)
                um[v[i]] = n - ans;
        }
 
        // Sort by ending position
        v.Sort((x, y) => x.second - y.second);
 
        // Traverse all the intervals
        for (int i = 0; i < n; i++) {
 
            // Store the starting and
            // ending point of the
            // ith interval
            int start = v[i].first;
            int end = v[i].second;
 
            // Set low and high
            int low = 0;
            int high = i - 1;
 
            // Store the required number
            // of intervals
            int ans = -1;
 
            // Apply binary search to
            // find the number of intervals
            // completely lying to the
            // left of the ith interval
            while (low <= high) {
                int mid = low + (high - low) / 2;
                if (v[mid].second < start) {
                    ans = mid;
                    low = mid + 1;
                }
                else {
                    high = mid - 1;
                }
            }
 
            // Increment um for v[i] by ans+1
            // if ans!=-1
            if (ans != -1)
                um[v[i]] = um[v[i]] + (ans + 1);
        }
 
        // Store the answer
        int res = 0;
 
        // Traverse the map
        foreach(var entry in um)
        {
            int second = entry.Value;
 
            // Update the overall answer
            res = Math.Max(res, n - second);
        }
 
        // Print the answer
        Console.WriteLine(res);
    }
 
    // Driver Code
    public static void Main(string[] args)
    {
 
        List<Pair> arr = new List<Pair>();
        arr.Add(new Pair(1, 2));
        arr.Add(new Pair(3, 4));
        arr.Add(new Pair(2, 5));
 
        int N = arr.Count;
 
        // Function Call
        FindMaxIntervals(arr, N);
    }
}
 
// This code is contributed by phasing17

Javascript

// JS code to implement the approach
 
// Function to find the maximum number of intervals that an interval can intersect
function findMaxIntervals(v) {
    // Sort the intervals by their starting position
    v.sort((a, b) => {
        if (a[0] !== b[0]) {
            return a[0] - b[0];
        } else {
            return a[1] - b[1];
        }
    });
    let n = v.length;
    // Use a dictionary to store the number of intervals that can intersect with each interval
    let um = new Map();
 
    // Iterate through all the intervals
    for (let i = 0; i < n; i++) {
        // Store the starting and ending point of the current interval
        let start = v[i][0];
        let end = v[i][1];
 
        let low = i + 1;
        let high = n - 1;
        let ans = -1;
        // Use binary search to find the number of intervals completely lying to the right of the current interval
        while (low <= high) {
            let mid = low + Math.floor((high - low) / 2);
            if (v[mid][0] > end) {
                ans = mid;
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
 
        // Increment the number of intersecting intervals in the dictionary
        if (ans !== -1) {
            um.set(v[i], n - ans);
        }
    }
 
    // Sort the intervals by their ending position
    v.sort((a, b) => {
        if (a[1] == b[1])
            return a[0] - b[0];
        return a[1] - b[1];
    })
 
    // Iterate through all the intervals
    for (var i = 0; i < n; i++)
    {
        // Store the starting and ending point of the current interval
        var start = v[i][0]
        var end = v[i][1]
 
        var low = 0
        var high = i - 1
        var ans = -1
        // Use binary search to find the number of intervals completely lying to the left of the current interval
        while (low <= high)
        {
            mid = low + Math.floor((high - low) / 2)
            if (v[mid][1] < start)
            {
                ans = mid
                low = mid + 1
            }
            else
                high = mid - 1
        }
 
        // Increment the number of intersecting intervals in the dictionary
        var key = v[i].join("#")
        if (!um.hasOwnProperty(key))
            um[key] = 0;
        if (ans != -1)
            um[key] += (ans + 1)
    }
 
    // Find the interval with the maximum number of non-intersecting intervals
    var res = 0
     
    var vals = Object.values(um)
    for (let val of vals)
        res = Math.max(res, n - val)
    console.log(res)
}
 
let arr = [[1, 2], [3, 4], [2, 5]]
findMaxIntervals(arr)
 
 
// This code is contributed by phasing17

Output

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