Given an N horizontal line segments are arranged on the X-axis of a 2D plane. The start and end point of each line segment is given in an Nx2 matrix lines[ ][ ], the task is to find the maximum number of intersections possible of any vertical line with the given N line segments.
Examples:
Input: N = 4, lines[][] = {{1, 3}, {2, 3}, {1, 2}, {4, 4}}
Output: 3
Explanation: A vertical line at X = 2 passes through {1, 3}, {2, 3}, {1, 2}, ie three of the given horizontal lines.Input: N = 3, lines[][] = {{1, 3}, {5, 6}, {3, 4}}
Output: 2
Explanation: A vertical line at X = 3 passes through two of the given horizontal lines which are the maximum possible.
Approach: This can be solved with the following idea:
Using hashMap, we can determine the maximum value among all the points and return it as a answer.
Follow the steps mentioned below to implement the idea:
- Take the n, the number of horizontal lines, and matrix lines[][].
- Create a map to store the number of lines at each x-coordinate.
- Iterate through each line and update the map accordingly.
- Initialize variables to keep track of the maximum number of intersections and a sum to keep track of the number of lines at each x-coordinate.
- Iterate through the map and update the sum and maximum accordingly.
- Return the maximum number of intersections.
Below is the implementation of the above approach:
C++
// C++ code for the above approach: #include <bits/stdc++.h> using namespace std; // Function to find maximum intersections int maxIntersections(vector<vector< int > > lines, int N) { // Create a map to store the number // of lines at each x-coordinate map< int , int > mp; // Iterate through each line and // update the map accordingly for ( int i = 0; i < lines.size(); i++) { int a = lines[i][0]; int b = lines[i][1]; mp[a]++; mp[b + 1]--; } // Initialize with minimum value // of integer int res = INT_MIN; int sum = 0; // Iterate through the map and update // the sum and maximum accordingly for ( auto it : mp) { sum += it.second; res = max(res, sum); } // Return the maximum number // of intersections return res; } // Driver code int main() { int n = 4; vector<vector< int > > mat = { { 1, 3 }, { 2, 3 }, { 1, 2 }, { 4, 4 } }; // Function call cout << maxIntersections(mat, n) << endl; } |
Java
// Java code for the above approach import java.util.*; public class MaxIntersections { // Function to find maximum intersections static int maxIntersections( int [][] lines, int N) { // Create a TreeMap to store the number // of lines at each x-coordinate TreeMap<Integer, Integer> map = new TreeMap<>(); // Iterate through each line and // update the map accordingly for ( int i = 0 ; i < N; i++) { int a = lines[i][ 0 ]; int b = lines[i][ 1 ]; map.put(a, map.getOrDefault(a, 0 ) + 1 ); map.put(b + 1 , map.getOrDefault(b + 1 , 0 ) - 1 ); } // Initialize with minimum value // of integer int res = Integer.MIN_VALUE; int sum = 0 ; // Iterate through the map and update // the sum and maximum accordingly for (Map.Entry<Integer, Integer> entry : map.entrySet()) { sum += entry.getValue(); res = Math.max(res, sum); } // Return the maximum number // of intersections return res; } // Driver code public static void main(String[] args) { int n = 4 ; int [][] mat = { { 1 , 3 }, { 2 , 3 }, { 1 , 2 }, { 4 , 4 } }; // Function call System.out.println(maxIntersections(mat, n)); } } |
Python3
# python code for the above approach: def max_intersections(lines, n): # Create a dictionary to store the number of lines # at each x-coordinate mp = {} # Iterate through each line and update the dictionary accordingly for line in lines: a = line[ 0 ] b = line[ 1 ] mp[a] = mp.get(a, 0 ) + 1 mp[b + 1 ] = mp.get(b + 1 , 0 ) - 1 # Initialize with minimum value of integer res = float ( '-inf' ) sum_ = 0 # Iterate through the dictionary and update the sum and # maximum accordingly for key, value in sorted (mp.items()): sum_ + = value res = max (res, sum_) # Return the maximum number of intersections return res # Driver code n = 4 lines = [[ 1 , 3 ], [ 2 , 3 ], [ 1 , 2 ], [ 4 , 4 ]] # Function call print (max_intersections(lines, n)) |
C#
using System; using System.Collections.Generic; class GFG { // Function to find maximum intersections static int MaxIntersections(List< int []> lines) { // Create a list to store events List<Tuple< int , int >> events = new List<Tuple< int , int >>(); // Populate the list with events foreach ( int [] line in lines) { int a = line[0]; int b = line[1]; events.Add( new Tuple< int , int >(a, 1)); events.Add( new Tuple< int , int >(b + 1, -1)); } // Sort the events by their x-coordinates events.Sort(); int res = 0; int count = 0; // Iterate through the events and // calculate intersections foreach ( var evt in events) { count += evt.Item2; res = Math.Max(res, count); } return res; } static void Main() { List< int []> lines = new List< int []> { new int [] { 1, 3 }, new int [] { 2, 3 }, new int [] { 1, 2 }, new int [] { 4, 4 } }; // Function call Console.WriteLine(MaxIntersections(lines)); } } |
Javascript
function maxIntersections(lines) { const mp = {}; // Iterate through each line and update the dictionary accordingly for (const line of lines) { const a = line[0]; const b = line[1]; mp[a] = (mp[a] || 0) + 1; mp[b + 1] = (mp[b + 1] || 0) - 1; } let res = Number.MIN_SAFE_INTEGER; let sum = 0; // Iterate through the dictionary and update the sum and maximum accordingly const sortedKeys = Object.keys(mp).sort((a, b) => a - b); for (const key of sortedKeys) { const value = mp[key]; sum += value; res = Math.max(res, sum); } // Return the maximum number of intersections return res; } // Example usage const n = 4; const lines = [[1, 3], [2, 3], [1, 2], [4, 4]]; console.log(maxIntersections(lines)); // Output: 3 |
3
Time Complexity: O(N*log(N))
Auxiliary Space: O(N)
Approach 2: Using Sorting and Two pointers approach
Following steps to solve the problem:
1. Store the start points and end points in two separate vectors – one for start point and one for end point.
2. Now, sort the both vectors.
3. Take two pointer i and j and loop from both end using while loop.
4. Check the line starting before ending point ( start point[i]<=end point[j] ). So increment intersections and pointer i++ and also update ans.
5. Else the line ending before new line starting ( start point[i]>end point[j] ) . So decrement intersections– and increment j++;
6. Return the final answer.
Below is the implementation of the above approach:
C++
// C++ code for the above approach: #include <bits/stdc++.h> using namespace std; // Function to find maximum intersxn int maxIntersections(vector<vector< int >> lines, int n) { vector< int > start_lns(n); // to store start point of each lines vector< int > end_lns(n); // to store end point of each lines //filling start point and end point from lines matrix for ( int i=0;i<n;i++) { start_lns[i] = lines[i][0]; end_lns[i] = lines[i][1]; } // sorting start points and end points vectors sort(start_lns.begin(), start_lns.end()); sort(end_lns.begin(), end_lns.end()); int i=0; int j=0; int intersxn=0; // count intersections of lines int ans=INT_MIN; // to store answer while (i<n && j<n) { // if new line starting before a line ending then increment intersection by 1 and update ans if (start_lns[i] <= end_lns[j]) { intersxn++; ans = max(ans, intersxn); i++; } // else decrement intersections by 1 else { intersxn--; j++; } } // return the ans return ans; } // Driver code int main() { int n = 4; vector<vector< int > > lines = { { 1, 3 }, { 2, 3 }, { 1, 2 }, { 4, 4 } }; // Function call cout << maxIntersections(lines, n) << endl; } |
Java
import java.util.Arrays; public class MaxIntersections { // Function to find maximum intersections static int maxIntersections( int [][] lines, int n) { int [] startLines = new int [n]; // To store the start point of each line int [] endLines = new int [n]; // To store the end point of each line // Filling start point and end point arrays from lines matrix for ( int i = 0 ; i < n; i++) { startLines[i] = lines[i][ 0 ]; endLines[i] = lines[i][ 1 ]; } // Sorting start points and end points arrays Arrays.sort(startLines); Arrays.sort(endLines); int i = 0 ; int j = 0 ; int intersections = 0 ; // Count intersections of lines int result = Integer.MIN_VALUE; // To store the answer while (i < n && j < n) { // If a new line starts before another line ends, increment intersections by 1 and update the result if (startLines[i] <= endLines[j]) { intersections++; result = Math.max(result, intersections); i++; } // Otherwise, decrement intersections by 1 else { intersections--; j++; } } // Return the result return result; } // Driver code public static void main(String[] args) { int n = 4 ; int [][] lines = { { 1 , 3 }, { 2 , 3 }, { 1 , 2 }, { 4 , 4 } }; // Function call System.out.println(maxIntersections(lines, n)); } } |
Python3
# Python code for the above approach: # Function to find maximum intersxn def maxIntersections(lines, n): start_lns = [] # to store start point of each lines end_lns = [] # to store end point of each lines #filling start point and end point from lines matrix for i in range (n): start_lns.append(lines[i][ 0 ]) end_lns.append(lines[i][ 1 ]) # sorting start points and end points vectors start_lns.sort() end_lns.sort() i = 0 j = 0 intersxn = 0 # count intersections of lines ans = float ( '-inf' ) # to store answer while (i<n and j<n): # if new line starting before a line ending then increment intersection by 1 and update ans if (start_lns[i] < = end_lns[j]): intersxn + = 1 ans = max (ans, intersxn) i + = 1 # else decrement intersections by 1 else : intersxn - = 1 j + = 1 # return the ans return ans # Driver code n = 4 lines = [ [ 1 , 3 ], [ 2 , 3 ], [ 1 , 2 ], [ 4 , 4 ] ] # Function call print (maxIntersections(lines, n)) |
3
Time Complexity: O(N*log(N)), as sorting the vectors so time complexity is O(n).
Auxiliary Space: O(N), as taking the vector so space complexity is O(n).
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!