Given n infinite vertical lines on an XY plane and m axis-aligned rectangles, find the total number of intersection points made by the lines and rectangles.
A vertical line creates exactly two intersection points with a rectangle if it strictly passes through the rectangle, one on the top horizontal side and one on the bottom horizontal side.
If a vertical line lies on the left or right vertical side of a rectangle, it is not counted as an intersection for that rectangle.
Method Signature
long countIntersectionPoints(List<Integer> verticalLines, List<String> rectangles)
- Each vertical line is represented only by its x-coordinate because every line is infinite in the y-direction.
verticalLines: each value represents the x-coordinate of one infinite vertical line.rectangles: each string is in format "leftX,bottomY,rightX,topY".- For every rectangle,
leftX < rightX and bottomY < topY.
- A line at x-coordinate
x intersects a rectangle only when leftX < x < rightX.
- Each valid line-rectangle crossing contributes exactly
2 intersection points.
- If two vertical lines have the same x-coordinate, they are counted as separate lines.
Input Format
verticalLines contains x-coordinates of vertical lines.rectangles contains rectangle coordinates as comma-separated strings.
Output Format
- Return the total number of intersection points as a
long.
- The output is deterministic because only the total count is returned.
Constraints
1 ≤ n ≤ 200,0001 ≤ m ≤ 200,000-1,000,000,000 ≤ verticalLines[i] ≤ 1,000,000,000-1,000,000,000 ≤ leftX < rightX ≤ 1,000,000,000-1,000,000,000 ≤ bottomY < topY ≤ 1,000,000,000
Examples
Example 1
countIntersectionPoints(verticalLines = List.of(1, 3, 5, 7), rectangles = List.of("0,0,4,2", "3,1,8,5"))
Output: 8
Explanation: In the first rectangle, lines 1 and 3 strictly pass through it, giving 4 points. In the second rectangle, lines 5 and 7 strictly pass through it, giving 4 more points. Line 3 lies on the rectangle boundary, so it is not counted.
Example 2
countIntersectionPoints(verticalLines = List.of(-2, 0, 2, 4), rectangles = List.of("-2,-1,2,3", "-5,0,5,10"))
Output: 10
Explanation: For the first rectangle, only line 0 is strictly inside, giving 2 points. For the second rectangle, lines -2, 0, 2, and 4 are strictly inside, giving 8 points. Total intersection points are 2 + 8 = 10.