Skip to content

Maximum Boxes Cut by Line

Level: L3-L4 Topics: Geometry, Sweep Line, Coordinate Compression

Problem Statement

You have a rectangular PCB (printed circuit board) with N rectangular components placed on it. Each component is axis-aligned and defined by its bounding box coordinates.

Find the maximum number of components that a single straight horizontal or vertical line can touch. A line "touches" a component if it intersects the component's rectangle, including its edges and corners.

Background & Constraints

  • N <= 1000 components.
  • The board dimensions are at most 10 cm, and lines can be placed at every micrometer (10^-6 meters), giving up to 10^4 possible positions per axis in theory.
  • Components may overlap with each other.
  • A line touching just the edge or corner of a rectangle counts as touching that component.
  • Components are given as (x1, y1, x2, y2) where (x1, y1) is the bottom-left and (x2, y2) is the top-right corner.

Examples

Input:

Components:
  A: (1, 1, 3, 4)
  B: (2, 5, 5, 7)
  C: (4, 2, 6, 6)
  D: (7, 1, 9, 3)

Horizontal line at y = 3: touches A (interior), C (interior), and D (top edge). Count = 3.

Horizontal line at y = 4: touches A (top edge), C (passes through interior). Count = 2.

Horizontal line at y = 5: touches B (bottom edge), C (passes through interior). Count = 2.

Vertical line at x = 3: touches A (right edge, x ∈ [1, 3]) and B (interior, x ∈ [2, 5]). Count = 2.

The maximum in this example is 3 (achieved with a horizontal line at y = 2 or y = 3).

Hints & Common Pitfalls

  • You do not need to check every micrometer position. A horizontal line only changes which components it touches when it crosses a component's top or bottom edge. So the only y-coordinates you need to check are the y1 and y2 values of all components (and similarly for vertical lines with x-coordinates).
  • This is a coordinate compression insight: with N components, there are at most 2N relevant positions per axis.
  • For each candidate line position, count how many components it intersects. A horizontal line at y = k touches component (x1, y1, x2, y2) if y1 <= k <= y2.
  • A brute-force approach over all 2N candidate positions, checking all N components, gives O(N^2) which is fine for N <= 1000.
  • A sweep line with a sorted event list can improve this further if needed.

Follow-Up Questions

  1. Diagonal lines: Allow the line to be at any angle, not just horizontal or vertical. How do you find the line that touches the maximum number of components? Consider that any optimal line can be defined by passing through two corners of two different components. This leads to an O(N^2) enumeration of candidate lines, each checked against all N components for O(N^3) total — or better with geometric tricks.