Diện tích lớn nhất miếng bánh sau khi cắt (Maximum Area of a Piece of Cake) trong C++

Cho bánh chữ nhật chiều cao h, chiều rộng w. Các mảng horizontalCuts, verticalCuts chỉ vị trí cắt. Tìm diện tích lớn nhất của một miếng bánh sau khi cắt, kết quả modulo 10^9+7.

Ví dụ

Đầu vào: h=5, w=4, hCuts=[1,2,4], vCuts=[1,3]
Đầu ra: 4.

Thuật toán

1. Sắp xếp cả hai mảng cắt.
2. Thêm biên: 0 và h vào hCuts; 0 và w vào vCuts.
3. Tìm khoảng cách lớn nhất giữa hai cắt ngang liên tiếp → maxH.
4. Tìm khoảng cách lớn nhất giữa hai cắt dọc liên tiếp → maxW.
5. Kết quả = (maxH * maxW) % MOD.

Triển khai C++

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
using ll = long long;

class Solution {
public:
    int maxArea(int h, int w, vector<int>& hCuts, vector<int>& vCuts) {
        sort(hCuts.begin(), hCuts.end());
        sort(vCuts.begin(), vCuts.end());
        hCuts.insert(hCuts.begin(), 0);
        hCuts.push_back(h);
        vCuts.insert(vCuts.begin(), 0);
        vCuts.push_back(w);
        int maxH = 0, maxW = 0;
        for (int i = 1; i < hCuts.size(); ++i) maxH = max(maxH, hCuts[i] - hCuts[i-1]);
        for (int i = 1; i < vCuts.size(); ++i) maxW = max(maxW, vCuts[i] - vCuts[i-1]);
        return (int)((1LL * maxH * maxW) % MOD);
    }
};

Độ phức tạp

• Thời gian: O(H log H + V log V) do sắp xếp.
• Không gian: O(1) thêm (sửa trực tiếp mảng đầu vào).

Kết quả kiểm thử

Đầu vào: 5,4,{1,2,4},{1,3}
Đầu ra: 4