题目描述

A prisoner is planning to escape from prison! The prison s gate consists of horizontal and vertical bars that are spaced one unit apart so the area of each hole between the bars is 1 x 1. The prisoner manages to remove certain bars to make some bigger holes. Determine the area of the largest hole in the gate after the bars are removed

样例

n = 6
m = 6
h = [4];
v = [2];

In the images below. the left image depicts the initial 
prison gate with n 6 horizontal and m=6 vertical bars. 
The area of the biggest hole in the bars is 1 x 1. The 
right image depicts that same gate after the prisoner 
removes horizontal bar 4 and vertical bar 2, at which 
point the area of the biggest hole in the bars becomes 
2 x2=4  

贪心

(类似此题： https://leetcode.com/problems/maximum-area-of-a-piece-of-cake-after-horizontal-and-vertical-cuts/)

C++ 代码

int prisonBreak(int n, int m, vector<int> &h, vector<int> &v)
{
    unordered_set<int> h_(h.begin(), h.end());
    unordered_set<int> v_(v.begin(), v.end());

    int maxh = 0, maxv = 0;
    int pre = -1;
    for(int i = 1; i <= n; i++)
    {
        if(h_.find(i) != h_.end()) continue;
        else
        {
            if(pre != -1)
                maxh = max(maxh, i - pre);
            pre = i;
        }
    }

    if(pre == -1) return -1;

    pre = -1;

    for(int i = 1; i <= m; i++)
    {
        if(v_.find(i) != v_.end()) continue;
        else
        {
            if(pre != -1)
                maxv = max(maxv, i - pre);
            pre = i;
        }
    }

    if(pre == -1) return -1;

    return maxh * maxv;
}