Maximum White Tiles Covered by a Carpet

Problem Statement

In this tutorial, we will solve the Maximum White Tiles Covered by a Carpet problem . We will provide the implementation of the solution in Python, Java, and C++.

Problem Description

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.

Examples

Example 1: Input: tiles = [[1,5],[10,11],[12,18],[20,25],[30,32]], carpetLen = 10 Output: 9 Explanation: Place the carpet starting on tile 10. It covers 9 white tiles, so we return 9. Note that there may be other places where the carpet covers 9 white tiles. It can be shown that the carpet cannot cover more than 9 white tiles. Example 2: Input: tiles = [[10,11],[1,1]], carpetLen = 2 Output: 2 Explanation: Place the carpet starting on tile 10. It covers 2 white tiles, so we return 2.

Constraints

• 1 <= tiles.length <= 5 * 104
• tiles[i].length == 2
• 1 <= li <= ri <= 109
• 1 <= carpetLen <= 109
• The tiles are non-overlapping.

Solution of Given Problem

Intuition and Approach

The problem can be solved using a brute force approach or an optimized Technique.

• Brute Force
• Optimized approach

Approach 1:Brute Force (Naive)

Brute Force Approach: In the brute force approach, we try placing the carpet starting at every possible position and calculate the number of tiles it covers. This approach is inefficient, especially for large inputs, but it provides a straightforward way to understand the problem.

Codes in Different Languages

C++

Written by @AmruthaPariprolu

#include <vector>
#include <algorithm>
#include <iostream>

int maxWhiteTilesBruteForce(std::vector<std::vector<int>>& tiles, int carpetLen) {
    std::sort(tiles.begin(), tiles.end());
    int maxCovered = 0;

    for (const auto& tile : tiles) {
        int start = tile[0];
        int end = start + carpetLen - 1;
        int covered = 0;

        for (const auto& t : tiles) {
            if (t[1] < start) continue;
            if (t[0] > end) break;
            covered += std::min(t[1], end) - std::max(t[0], start) + 1;
        }
        maxCovered = std::max(maxCovered, covered);
    }
    return maxCovered;
}

int main() {
    std::vector<std::vector<int>> tiles = {{1, 5}, {10, 11}, {12, 18}, {20, 25}, {30, 32}};
    int carpetLen = 10;
    std::cout << "Maximum white tiles covered: " << maxWhiteTilesBruteForce(tiles, carpetLen) << std::endl;
    return 0;
}

Java

Written by @AmruthaPariprolu

import java.util.*;

public class Main {
    public static int maxWhiteTilesBruteForce(int[][] tiles, int carpetLen) {
        Arrays.sort(tiles, Comparator.comparingInt(a -> a[0]));
        int maxCovered = 0;

        for (int[] tile : tiles) {
            int start = tile[0];
            int end = start + carpetLen - 1;
            int covered = 0;

            for (int[] t : tiles) {
                if (t[1] < start) continue;
                if (t[0] > end) break;
                covered += Math.min(t[1], end) - Math.max(t[0], start) + 1;
            }
            maxCovered = Math.max(maxCovered, covered);
        }
        return maxCovered;
    }

    public static void main(String[] args) {
        int[][] tiles = {{1, 5}, {10, 11}, {12, 18}, {20, 25}, {30, 32}};
        int carpetLen = 10;
        System.out.println("Maximum white tiles covered: " + maxWhiteTilesBruteForce(tiles, carpetLen));
    }
}

Python

Written by @AmruthaPariprolu

def max_white_tiles_brute_force(tiles, carpet_len):
    tiles.sort()
    max_covered = 0

    for start, _ in tiles:
        end = start + carpet_len - 1
        covered = 0

        for l, r in tiles:
            if r < start:
                continue
            if l > end:
                break
            covered += min(r, end) - max(l, start) + 1

        max_covered = max(max_covered, covered)
    return max_covered

tiles = [[1, 5], [10, 11], [12, 18], [20, 25], [30, 32]]
carpet_len = 10
print("Maximum white tiles covered:", max_white_tiles_brute_force(tiles, carpet_len))

Complexity Analysis

• Time Complexity: $O(n^2)$
• because we iterate through all possible start points and check each tile range for each starting point.
• Space Complexity: $O(1)$
• as we only use a few extra variables for counting.

---

Authors:

Loading...