Link to the Problem
Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts
Thought Process
Each cut in the cake, divides the cake into pieces with certain height and certain width. We want to maximize the area, so the best piece would the one with maximum height among all pieces and maximum width among all pieces.
So the only task for us is to find what would be the height and width of each piece after all cuts and then find the piece with maximum height and width. Area of the piece is simply the multiplication of the height and the width.
Algorithm
- Get maximum height of a piece among all pieces.
- Sort the horizontal cuts array so that each horizontal cut would result in pieces of certain height.
- Find the max among them.
- Similarly for the width.
- Multiply height and width.
Code
| class Solution { | |
| const int mod = (1e9)+7; // As the question expects. | |
| int getMax(int length, vector<int> &cuts) { | |
| sort(cuts.begin(), cuts.end()); // Sort so that we will easily get the thickness | |
| // of each piece after cutting it. | |
| int n = cuts.size(); | |
| int maxCut = max(length-cuts[n-1], // Thickness of the last piece. | |
| cuts[0]); // Thickness of the first piece. | |
| for (int i=1; i<n; i++) { // For each cut - | |
| maxCut = max(maxCut, cuts[i]-cuts[i-1]); // Thickness of each piece. | |
| } | |
| return maxCut; | |
| } | |
| public: | |
| int maxArea(int height, int width, vector<int>& h, vector<int>& w) { | |
| long maxHeight = getMax(height, h); | |
| long maxWidth = getMax(width, w); | |
| return (int)(maxHeight * maxWidth % mod); | |
| } | |
| }; |
Is there anything that is still unclear? Let me know in the comments and I can elaborate further.
Don’t forget like & share the post, and subscribe to the blog to get notifications whenever solution to a new problem is added.
Happy Coding!
Similar Problems
Leetcode #492: Construct the Rectangle
