Largest Sheet After Cuts

Medium

A rectangular plywood sheet is height tall and width wide. It is cut all the way through: row_cuts[i] is the distance from the top edge to the i-th horizontal cut, and col_cuts[j] is the distance from the left edge to the j-th vertical cut. The cuts are listed in no particular order. After all the cuts, the sheet falls apart into rectangular pieces. Return the area of the largest piece modulo 10⁹ + 7.

Example 1

height=6, width=5, row_cuts=[2, 5], col_cuts=[3] → 9

Along the height the strips are 2, 3 and 1; along the width, 3 and 2. The largest piece is 3 × 3 = 9.

Example 2

height=4, width=7, row_cuts=[1], col_cuts=[6, 2] → 12

Cuts may come in any order. Strips along the height are 1 and 3, along the width 2, 4 and 1: 3 × 4 = 12.

Example 3

height=2, width=2, row_cuts=[1], col_cuts=[1] → 1

Constraints

2 ≤ height, width ≤ 10⁹
1 ≤ len(row_cuts) ≤ min(height - 1, 10⁵)
1 ≤ len(col_cuts) ≤ min(width - 1, 10⁵)
1 ≤ row_cuts[i] < height, 1 ≤ col_cuts[j] < width
All values in row_cuts are distinct, and so are those in col_cuts

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Greedy Array Sorting

Similar problems

Biggest Number From Pieces Medium Studios for Recording Sessions Medium Low, High, Low Medium Strictly Low, High, Low Medium Fewest Meetings to Cancel Medium

Input

height=6, width=5, row_cuts=[2, 5], col_cuts=[3]

Expected

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