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 intersectionsint 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 codeint 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 approachimport 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 coden = 4lines = [[1, 3], [2, 3], [1, 2], [4, 4]]# Function callprint(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 usageconst n = 4;const lines = [[1, 3], [2, 3], [1, 2], [4, 4]];console.log(maxIntersections(lines)); // Output: 3 |
Output
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 codeint 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 intersxndef 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 coden = 4lines = [ [ 1, 3 ], [ 2, 3 ], [ 1, 2 ], [ 4, 4 ] ]# Function callprint(maxIntersections(lines, n)) |
Output
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).
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!
