|
| 1 | +// Source : https://leetcode.com/problems/number-of-rectangles-that-can-form-the-largest-square/ |
| 2 | +// Author : Hao Chen |
| 3 | +// Date : 2021-03-27 |
| 4 | + |
| 5 | +/***************************************************************************************************** |
| 6 | + * |
| 7 | + * You are given an array rectangles where rectangles[i] = [li, wi] represents the i^th rectangle of |
| 8 | + * length li and width wi. |
| 9 | + * |
| 10 | + * You can cut the i^th rectangle to form a square with a side length of k if both k <= li and k <= |
| 11 | + * wi. For example, if you have a rectangle [4,6], you can cut it to get a square with a side length |
| 12 | + * of at most 4. |
| 13 | + * |
| 14 | + * Let maxLen be the side length of the largest square you can obtain from any of the given rectangles. |
| 15 | + * |
| 16 | + * Return the number of rectangles that can make a square with a side length of maxLen. |
| 17 | + * |
| 18 | + * Example 1: |
| 19 | + * |
| 20 | + * Input: rectangles = [[5,8],[3,9],[5,12],[16,5]] |
| 21 | + * Output: 3 |
| 22 | + * Explanation: The largest squares you can get from each rectangle are of lengths [5,3,5,5]. |
| 23 | + * The largest possible square is of length 5, and you can get it out of 3 rectangles. |
| 24 | + * |
| 25 | + * Example 2: |
| 26 | + * |
| 27 | + * Input: rectangles = [[2,3],[3,7],[4,3],[3,7]] |
| 28 | + * Output: 3 |
| 29 | + * |
| 30 | + * Constraints: |
| 31 | + * |
| 32 | + * 1 <= rectangles.length <= 1000 |
| 33 | + * rectangles[i].length == 2 |
| 34 | + * 1 <= li, wi <= 10^9 |
| 35 | + * li != wi |
| 36 | + ******************************************************************************************************/ |
| 37 | + |
| 38 | +class Solution { |
| 39 | +public: |
| 40 | + int countGoodRectangles(vector<vector<int>>& rectangles) { |
| 41 | + return countGoodRectangles2(rectangles); |
| 42 | + return countGoodRectangles1(rectangles); |
| 43 | + } |
| 44 | + |
| 45 | + int countGoodRectangles1(vector<vector<int>>& rectangles) { |
| 46 | + int maxLen = 0; |
| 47 | + for(auto& rect : rectangles) { |
| 48 | + int len = min(rect[0], rect[1]); |
| 49 | + maxLen = max(maxLen, len); |
| 50 | + } |
| 51 | + |
| 52 | + int cnt = 0; |
| 53 | + for(auto& rect : rectangles) { |
| 54 | + if (maxLen <= rect[0] && maxLen <= rect[1]) cnt++; |
| 55 | + } |
| 56 | + return cnt; |
| 57 | + } |
| 58 | + |
| 59 | + int countGoodRectangles2(vector<vector<int>>& rectangles) { |
| 60 | + int maxLen = 0; |
| 61 | + int cnt = 0; |
| 62 | + for(auto& rect : rectangles) { |
| 63 | + int len = min(rect[0], rect[1]); |
| 64 | + if (len > maxLen ) { |
| 65 | + cnt = 1; |
| 66 | + maxLen = len; |
| 67 | + }else if (len == maxLen ) { |
| 68 | + cnt++; |
| 69 | + } |
| 70 | + } |
| 71 | + |
| 72 | + return cnt; |
| 73 | + } |
| 74 | +}; |
0 commit comments