技术问询：如何计算单条直线可穿过的最大矩形数量

Great question! First off, let's clear up one thing: dynamic programming isn't the right approach here. Instead, we can use a combination of event-based scanning and critical slope enumeration to solve this efficiently. Let's break this down step by step.

First, Handle Edge Cases: Vertical and Horizontal Lines #

These are straightforward and worth tackling separately before diving into general slopes:

• Vertical Lines (x = c): A vertical line passes through a rectangle if the line's x-coordinate c falls between the rectangle's left (x1) and right (x2) bounds. To find the maximum count:
  • Collect all rectangle boundaries: mark each x1 as a +1 event (we enter the rectangle) and each x2 as a -1 event (we exit).
  • Sort all events by their x-coordinate. As you iterate through them, keep a running count of how many rectangles you're currently passing through, and track the maximum value.
• Horizontal Lines (y = c): This works exactly like the vertical case, but using the rectangle's bottom (y1) and top (y2) bounds instead.

Core Idea for General Slopes #

Here's the key insight: the optimal line (the one passing through the most rectangles) will always pass through two vertices of the given rectangles (or a vertex and an edge midpoint, but vertex pairs cover all critical slopes where the count of overlapping rectangles changes).

So we can enumerate all possible slopes from pairs of vertices, then for each slope, calculate how many rectangles a line with that slope can pass through.

Step-by-Step for General Slopes #

1. Collect All Vertices: For each rectangle, grab its four corners: (x1,y1), (x1,y2), (x2,y1), (x2,y2). That gives us 4n total points.
2. Enumerate Unique Slopes:
   • Iterate over every pair of distinct points. Calculate the slope between them. To avoid floating-point precision issues, store slopes as reduced fractions (e.g., slope 2/4 becomes 1/2, with a positive denominator).
   • Skip duplicate slopes—no need to calculate the same case multiple times.
3. Convert Rectangles to Intervals for Each Slope:
   For a given slope k, a line y = kx + b passes through a rectangle [x1,x2]×[y1,y2] if b falls within a specific interval. Here's how to compute that interval:
   • If k > 0: The interval is [y1 - k*x2, y2 - k*x1]
   • If k < 0: The interval is [y2 - k*x1, y1 - k*x2]
     (This comes from rearranging the line equation to find valid b values that keep y within the rectangle's bounds for some x in [x1,x2].)
4. Count Maximum Overlapping Intervals:
   • For each rectangle's interval, create two events: (interval_start, +1) and (interval_end, -1).
   • Sort these events by their b value. If two events have the same b, process the +1 event first—this ensures we count overlapping intervals correctly.
   • Iterate through the sorted events, maintaining a running count of overlapping intervals. Track the maximum count here—that's the number of rectangles a line with this slope can pass through.

Optimizations & Notes #

• Skip Redundant Cases: We already handled horizontal lines (slope 0) earlier, so we can skip any vertex pairs that give a slope of 0 to avoid redundant work.
• Avoid Zero Denominators: When two points have the same x-coordinate (vertical line), we already handled this case, so skip these pairs too.
• Precision Matters: Using fractions instead of floats for slopes prevents errors from floating-point rounding, which is crucial for correctly grouping identical slopes.

Time Complexity #

• Vertical/horizontal line handling: O(n log n) (sorting events)
• General slope handling: Worst-case O(n³ log n) (we have O(n²) unique slopes, each requiring O(n log n) work to process intervals). This is feasible for most algorithm problem constraints (e.g., n ≤ 100).

Example #

Suppose we have two rectangles: [0,2]×[0,2] and [1,3]×[1,3]. The line y = x (slope 1) passes through both. For slope 1, each rectangle's interval for b is [-2, 2]—so the intervals fully overlap, giving a count of 2, which is the maximum.

内容的提问来源于stack exchange，提问作者Tapan Vaishnav