Corner Boxes Over Pins

Medium

Rectangular boxes lie on a plane, each with its bottom-left corner at the origin. Box boxes[i] = [w, h] spans from (0, 0) to (w, h). You also get pins pins[j] = [x, y], which are points on the plane. A box covers a pin when 0 ≤ x ≤ w and 0 ≤ y ≤ h; pins on the edge of a box count as covered. Return an array as long as pins whose entry j is the number of boxes covering pins[j]. Heights are tiny while widths are huge; make use of that.

Example 1

boxes=[[5, 3], [2, 8], [7, 7]], pins=[[2, 3], [6, 5], [8, 1]] → [3, 1, 0]

Pin (2, 3) is covered by all three boxes. Pin (6, 5) only by [7, 7]: both [5, 3] and [2, 8] are too narrow. Pin (8, 1) is covered by none, since every box is narrower than 8.

Example 2

boxes=[[4, 4]], pins=[[4, 4], [1, 5]] → [1, 0]

A pin on the corner of a box counts as covered; pin (1, 5) sits above the box.

Constraints

1 ≤ len(boxes), len(pins) ≤ 5·10⁴
1 ≤ w, x ≤ 10⁹
1 ≤ h, y ≤ 100
All boxes are distinct, and so are all pins

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Binary Indexed Tree Array Hash Table Binary Search Sorting

Similar problems

Pairs With a Fixed Gap Medium Words Hidden in a Text Medium Weight by the Earliest Letter Medium Shuttle Driver Earnings Medium Squaring Ladder Medium

Input

boxes=[[5, 3], [2, 8], [7, 7]], pins=[[2, 3], [6, 5], [8, 1]]

Expected

[3, 1, 0]

Run checks the first 3 tests in your browser. Submit checks all 59 tests on the server, hidden ones included.