Practice/Meta/Leetcode 2312. Selling Pieces of Wood

Leetcode 2312. Selling Pieces of Wood

CodingOptional

Problem

You are given a wooden board with dimensions m rows by n columns. You also have a list of prices, where each entry specifies that a piece of wood with certain dimensions can be sold for a given amount.

Each price entry is represented as [height, width, price], meaning a piece that is exactly height rows tall and width columns wide can be sold for price dollars.

You can cut the board as many times as you want using these rules:

• Horizontal cuts: Cut straight across the entire width at any row boundary (splitting the board into top and bottom pieces)
• Vertical cuts: Cut straight down the entire height at any column boundary (splitting the board into left and right pieces)
• No rotation: Pieces cannot be rotated, so a 2×3 piece is different from a 3×2 piece

Your goal is to maximize the total revenue by optimally cutting the board and selling the resulting pieces. If a piece doesn't have a listed price, it has a value of 0.

Requirements

1. Determine the optimal cutting strategy to maximize total revenue
2. Consider selling the entire board if that's most profitable
3. Consider all possible horizontal and vertical cuts at each step
4. Return the maximum revenue achievable

Constraints

• 1 ≤ m, n ≤ 200
• 0 ≤ prices.length ≤ 2000
• prices[i].length == 3
• 1 ≤ height_i ≤ m
• 1 ≤ width_i ≤ n
• 1 ≤ price_i ≤ 10^6
• All price entries have unique (height, width) pairs

Examples

Example 1:

` Input: m = 3, n = 5, prices = [[1,4,2], [2,2,7], [2,1,3]] Output: 19 Explanation:

• Cut horizontally after row 1, creating pieces of size 1×5 and 2×5
• The 1×5 piece: cut vertically after column 4 to get 1×4 (sell for 2) and 1×1 (sell for 0)
• The 2×5 piece: cut vertically after column 1 to get 2×1 (sell for 3) and 2×4
• The 2×4 piece: cut vertically at column 2 to get two 2×2 pieces (each sells for 7)
• Total: 2 + 0 + 3 + 7 + 7 = 19 `

Example 2:

Input: m = 2, n = 3, prices = [[2,3,10]] Output: 10 Explanation: The entire board is 2×3 and can be sold directly for 10, which is optimal.

Example 3:

Input: m = 1, n = 1, prices = [] Output: 0 Explanation: No prices are available, so the board has no value.