Maximum White Tiles Covered by a Carpet LeetCode solution in Rust

1
impl Solution {
2
  pub fn maximum_white_tiles(mut tiles: Vec<Vec<i32>>, carpet_len: i32) -> i32 {
3
    let n = tiles.len();
4
    tiles.sort_by(|a, b| a[0].cmp(&b[0]));
5

6
    let mut stack = vec![tiles[0][1] - tiles[0][0] + 1];
7
    for i in 1..n {
8
      stack.push(tiles[i][0] - tiles[i - 1][1] - 1);
9
      stack.push(tiles[i][1] - tiles[i][0] + 1);
10
    }
11

12
    let n = stack.len();
13
    let mut memo = vec![(0, 0, false); n + 1];
14

15
    for i in 0..n {
16
      memo[i + 1].0 = memo[i].0;
17
      memo[i + 1].1 = memo[i].1;
18
      memo[i + 1].0 += stack[i];
19
      if i % 2 == 0 {
20
        memo[i + 1].1 += stack[i];
21
        memo[i + 1].2 = true;
22
      }
23
    }
24

25
    let mut max = 0;
26
    let mut ri = 0;
27
    for li in 0..n {
28
      while ri < n && memo[ri].0 - memo[li].0 <= carpet_len {
29
        ri += 1;
30
      }
31

32
      let sum = memo[ri].0 - memo[li].0;
33
      let score = memo[ri].1 - memo[li].1;
34
      if memo[ri].2 {
35
        if sum < carpet_len {
36
          max = std::cmp::max(max, score);
37
        } else {
38
          let over = sum - carpet_len;
39
          let actual_score = score - over;
40
          max = std::cmp::max(max, actual_score);
41
        }
42
      } else {
43
        max = std::cmp::max(max, score);
44
      }
45
    }
46

47
    max.min(carpet_len)
48
  }
49
}