Maximum white tiles covered by a carpet

Array Binary Search Greedy Sliding Window Sorting Prefix Sum

35.7% acceptance

Feb 25, 2026

838

You are given a 2D integer array tiles where tiles[i] = [li, ri] represents that every tile j in the range li <= j <= ri is colored white. You are also given an integer carpetLen, the length of a single carpet that can be placed anywhere. Return the maximum number of white tiles that can be covered by the carpet.

Solution

Rust

Time O(n log n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn maximum_white_tiles(mut tiles: Vec<Vec<i32>>, carpet_len: i32) -> i32 {
    tiles.sort_unstable_by_key(|t| t[0]);
    let n = tiles.len();
    // Prefix sums of white tiles
    let mut prefix = vec![0i64; n + 1];
    for i in 0..n {
      prefix[i + 1] = prefix[i] + (tiles[i][1] - tiles[i][0] + 1) as i64;
    }

    let mut ans = 0i32;
    for i in 0..n {
      let start = tiles[i][0];
      let end = start + carpet_len - 1;
      // Find last tile starting <= end using binary search
      let j = tiles.partition_point(|t| t[0] <= end);
      // j is the number of tiles with start <= end, so tiles[0..j] start within carpet

      // Count tiles fully within [start, end]
      // Tiles 0..i all start before start
      // Tiles i..j: tiles[i..j-1] all start <= end
      // But we also need to check if they end within carpet

      let covered = if j == 0 {
        0
      } else {
        let last = j - 1;
        if tiles[last][1] <= end {
          // All tiles from i to last are fully covered
          prefix[j] - prefix[i]
        } else {
          // tiles[last] partially covered
          let partial = (end - tiles[last][0] + 1).max(0) as i64;
          prefix[last] - prefix[i] + partial
        }
      };
      ans = ans.max(covered as i32);
    }
    ans
  }
}