2271. Maximum White Tiles Covered by a Carpet Medium

1/**
2 * [2271] Maximum White Tiles Covered by a Carpet
3 *
4 * You are given a 2D integer array tiles where tiles[i] = [li, ri] represents that
5 * every tile j in the range li <= j <= ri is colored white.
6 * You are also given an integer carpetLen, the length of a single carpet that can
7 * be placed anywhere.
8 * Return the maximum number of white tiles that can be covered by the carpet.
9 *  
10 * Example 1:
11 * <img alt="" src="https://assets.leetcode.com/uploads/2022/03/25/example1drawio3.png" style="width: 644px; height: 158px;" />
12 * Input: tiles = [[1,5],[10,11],[12,18],[20,25],[30,32]], carpetLen = 10
13 * Output: 9
14 * Explanation: Place the carpet starting on tile 10.
15 * It covers 9 white tiles, so we return 9.
16 * Note that there may be other places where the carpet covers 9 white tiles.
17 * It can be shown that the carpet cannot cover more than 9 white tiles.
18 *
19 * Example 2:
20 * <img alt="" src="https://assets.leetcode.com/uploads/2022/03/24/example2drawio.png" style="width: 231px; height: 168px;" />
21 * Input: tiles = [[10,11],[1,1]], carpetLen = 2
22 * Output: 2
23 * Explanation: Place the carpet starting on tile 10.
24 * It covers 2 white tiles, so we return 2.
25 *
26 *  
27 * Constraints:
28 *
29 * 1 <= tiles.length <= 5 * 10^4
30 * tiles[i].length == 2
31 * 1 <= li <= ri <= 10^9
32 * 1 <= carpetLen <= 10^9
33 * The tiles are non-overlapping.
34 *
35 */
36pub struct Solution {}
37
38// problem: https://leetcode.com/problems/maximum-white-tiles-covered-by-a-carpet/
39// discuss: https://leetcode.com/problems/maximum-white-tiles-covered-by-a-carpet/discuss/?currentPage=1&orderBy=most_votes&query=
40
41// submission codes start here
42use std::cmp;
43impl Solution {
44    pub fn maximum_white_tiles(tiles: Vec<Vec<i32>>, carpet_len: i32) -> i32 {
45        let mut tiles_sorted = tiles.clone();
46        tiles_sorted.sort();
47
48        let mut max = 0;
49        let mut i = 0;
50        let mut j = 0;
51        let mut current = 0;
52
53        while max < carpet_len && i < tiles_sorted.len() {
54            // move i
55            if j == i || tiles_sorted[j][0] + carpet_len > tiles_sorted[i][1] {
56                current += cmp::min(carpet_len, tiles_sorted[i][1] - tiles_sorted[i][0] + 1);
57                max = cmp::max(max, current);
58                i += 1;
59            // move j
60            } else {
61                let parts = cmp::max(0, tiles_sorted[j][0] + carpet_len - tiles_sorted[i][0]);
62                max = cmp::max(max, current + parts);
63                current -= tiles_sorted[j][1] - tiles_sorted[j][0] + 1;
64                j += 1;
65            }
66        }
67        max
68    }
69}
70
71// submission codes end
72
73#[cfg(test)]
74mod tests {
75    use super::*;
76
77    #[test]
78    fn test_2271() {
79        assert_eq!(
80            Solution::maximum_white_tiles(
81                vec![
82                    vec![30, 32],
83                    vec![1, 5],
84                    vec![10, 11],
85                    vec![12, 18],
86                    vec![20, 25],
87                ],
88                10
89            ),
90            9
91        );
92    }
93}
94