Problem Description

You have a collection of tile segments on a number line, where each segment represents a continuous range of white tiles. Each tile segment is given as [l, r], meaning all integer positions from l to r (inclusive) contain white tiles.

You also have a carpet of fixed length carpetLen that you can place at any position on the number line. The carpet will cover exactly carpetLen consecutive positions starting from wherever you place it.

Your goal is to find the optimal placement of the carpet such that it covers the maximum number of white tiles possible. The carpet can partially cover tile segments - it doesn't need to align perfectly with segment boundaries.

For example, if you have tiles at positions [1, 2] and [5, 7] with a carpet of length 4, you could place the carpet starting at position 1 to cover tiles 1 and 2 (covering 2 tiles total), or starting at position 4 to cover tiles 5, 6, and 7 (covering 3 tiles total).

The function should return the maximum number of white tiles that can be covered by placing the carpet optimally.

Intuition

The key insight is that to maximize coverage, we should always start the carpet at the beginning of some tile segment. Why? If the carpet starts in empty space before a segment, we can shift it forward to the segment's start without losing any coverage while potentially gaining more tiles.

Once we realize the carpet should start at a segment's beginning, we can use a sliding window approach. For each potential starting position (the left edge of each tile segment), we need to determine how many tiles the carpet can cover from that position.

The challenge is efficiently calculating coverage when the carpet might partially overlap with a segment. If a carpet of length carpetLen starts at position li (left edge of segment i), it extends to position li + carpetLen - 1. We need to count:

1. All complete segments that fall entirely within the carpet's range
2. Any partial coverage of a segment that extends beyond the carpet's right edge

This naturally leads to a two-pointer technique:

• The first pointer i iterates through each segment as a potential starting position
• The second pointer j tracks which segments are fully or partially covered by the carpet

As we move the starting position from one segment to the next, we can maintain a running sum s of fully covered segments. When we encounter a segment that's only partially covered (the carpet ends somewhere in the middle of it), we calculate the partial coverage as li + carpetLen - tiles[j][0], which represents how many tiles from that segment fall within the carpet's range.

The sliding window works because as we move to later starting positions, we remove the contribution of earlier segments that are no longer covered and add new segments that come into range, avoiding redundant recalculation.

Learn more about Greedy, Binary Search, Prefix Sum, Sorting and Sliding Window patterns.

Solution Approach

The implementation uses a sliding window with two pointers to efficiently find the maximum coverage:

Step 1: Sort the tiles

tiles.sort()

First, we sort the tiles by their starting positions to process them in order from left to right.

Step 2: Initialize variables

• s: Running sum of tiles in fully covered segments
• ans: Maximum tiles covered so far
• j: Right pointer tracking which segments are within carpet range
• i: Left pointer iterating through each segment as a potential carpet starting position

Step 3: Main sliding window logic

For each segment i with left edge li and right edge ri:

while j < n and tiles[j][1] - li + 1 <= carpetLen:
    s += tiles[j][1] - tiles[j][0] + 1
    j += 1

This loop adds all segments that can be fully covered when the carpet starts at li. The condition tiles[j][1] - li + 1 <= carpetLen checks if segment j's right edge is within the carpet's reach (carpet extends from li to li + carpetLen - 1).

Step 4: Handle partial coverage

if j < n and li + carpetLen > tiles[j][0]:
    ans = max(ans, s + li + carpetLen - tiles[j][0])
else:
    ans = max(ans, s)

• If there's a segment j that's partially covered (carpet ends somewhere within it), we add the partial coverage: li + carpetLen - tiles[j][0]
• Otherwise, only fully covered segments contribute to the count

Step 5: Slide the window

s -= ri - li + 1

Before moving to the next starting position, we remove the current segment i from the running sum since it will no longer be covered when we start the carpet at segment i+1.

The algorithm maintains the invariant that s contains the sum of all fully covered segments for the current carpet position, while j always points to the first segment that's either partially covered or completely outside the carpet's range.

Time Complexity: O(n log n) for sorting plus O(n) for the sliding window, giving O(n log n) overall. Space Complexity: O(1) excluding the sorting space.

Example Walkthrough

Let's walk through a concrete example to illustrate the solution approach.

Input: tiles = [[1, 2], [5, 7], [9, 10]], carpetLen = 4

Step 1: Initial Setup

• After sorting (already sorted): tiles = [[1, 2], [5, 7], [9, 10]]
• Initialize: s = 0, ans = 0, j = 0, n = 3

Step 2: Try carpet starting at position 1 (segment i=0)

• Carpet covers positions 1 to 4 (since carpetLen = 4)
• Check which segments can be fully covered:
  • Segment [1, 2]: length = 2, distance from start = 2-1+1 = 2 ≤ 4 ✓ (fully covered)
    • Add to sum: s = 0 + 2 = 2, move j to 1
  • Segment [5, 7]: length = 3, distance from start = 7-1+1 = 7 > 4 ✗ (not fully covered)
    • Stop the while loop
• Check partial coverage of segment j=1 ([5, 7]):
  • Carpet ends at position 4, segment starts at 5
  • No partial coverage (4 < 5)
• Update answer: ans = max(0, 2) = 2
• Slide window: Remove segment i=0 from sum: s = 2 - 2 = 0

Step 3: Try carpet starting at position 5 (segment i=1)

• Carpet covers positions 5 to 8
• Check which segments can be fully covered:
  • Segment [5, 7]: length = 3, distance from start = 7-5+1 = 3 ≤ 4 ✓ (fully covered)
    • Add to sum: s = 0 + 3 = 3, move j to 2
  • Segment [9, 10]: length = 2, distance from start = 10-5+1 = 6 > 4 ✗ (not fully covered)
    • Stop the while loop
• Check partial coverage of segment j=2 ([9, 10]):
  • Carpet ends at position 8, segment starts at 9
  • No partial coverage (8 < 9)
• Update answer: ans = max(2, 3) = 3
• Slide window: Remove segment i=1 from sum: s = 3 - 3 = 0

Step 4: Try carpet starting at position 9 (segment i=2)

• Carpet covers positions 9 to 12
• Check which segments can be fully covered:
  • Segment [9, 10]: length = 2, distance from start = 10-9+1 = 2 ≤ 4 ✓ (fully covered)
    • Add to sum: s = 0 + 2 = 2, move j to 3
• No more segments to check
• Update answer: ans = max(3, 2) = 3

Final Answer: 3

The optimal placement is starting the carpet at position 5, which covers all 3 tiles in segment [5, 7].

Solution Implementation

Time and Space Complexity

Time Complexity: O(n log n) where n is the number of tile intervals.

• The sorting operation takes O(n log n) time.
• The main loop iterates through each tile interval with index i from 0 to n-1, which is O(n).
• The inner while loop might seem like it creates nested iteration, but each tile interval is visited by the pointer j at most once throughout the entire execution. The pointer j only moves forward and never resets, making it a two-pointer technique with amortized O(n) complexity.
• Inside the loops, all operations (comparisons, arithmetic operations, max calculations) are O(1).
• Therefore, the overall time complexity is dominated by the sorting: O(n log n).

Space Complexity: O(1) if we don't count the space used by sorting, or O(n) if we consider the space used by the sorting algorithm.

• The algorithm uses a constant amount of extra variables: n, s, ans, j, i, li, and ri.
• No additional data structures are created that scale with the input size.
• However, the sort() method in Python uses Timsort, which requires O(n) auxiliary space in the worst case.
• If we consider only the extra space used by the algorithm itself (excluding sorting), the space complexity is O(1).
• If we include the sorting space overhead, the space complexity is O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Off-by-One Error in Carpet Coverage Calculation

A frequent mistake is incorrectly calculating whether a tile segment fits entirely within the carpet's range. The condition tiles[j][1] - li + 1 <= carpetLen includes the "+1" because both endpoints are inclusive.

Incorrect approach:

# Wrong: Missing the +1
while j < n and tiles[j][1] - li <= carpetLen:

Why it fails: This would incorrectly include segments that extend beyond the carpet. For example, if carpet starts at position 5 with length 3 (covering positions 5, 6, 7), and a segment is [5, 8], the wrong condition would evaluate to 8 - 5 = 3 <= 3 (True), incorrectly assuming the entire segment fits.

Correct approach:

# Correct: Include +1 for inclusive range
while j < n and tiles[j][1] - li + 1 <= carpetLen:

2. Forgetting to Handle Partial Coverage Edge Cases

Another pitfall is only considering fully covered segments and ignoring partial coverage of the next segment that extends beyond the carpet.

Incorrect approach:

# Wrong: Only considering fully covered segments
for left_index, (left_bound, right_bound) in enumerate(tiles):
    while right_index < num_tiles and tiles[right_index][1] - left_bound + 1 <= carpetLen:
        current_coverage += tiles[right_index][1] - tiles[right_index][0] + 1
        right_index += 1
  
    # Missing partial coverage calculation!
    max_coverage = max(max_coverage, current_coverage)

Why it fails: This misses cases where the optimal solution involves partial coverage. For instance, with tiles [[1,1], [10,14]] and carpetLen=5, starting the carpet at position 10 covers all 5 tiles in the second segment, but without partial coverage logic, we'd only consider the single tile at position 1.

Correct approach:

# Check for partial coverage of the next segment
if right_index < num_tiles and left_bound + carpetLen > tiles[right_index][0]:
    partial_coverage = left_bound + carpetLen - tiles[right_index][0]
    max_coverage = max(max_coverage, current_coverage + partial_coverage)
else:
    max_coverage = max(max_coverage, current_coverage)

3. Not Maintaining the Sliding Window Properly

Failing to remove the current segment from current_coverage when sliding the window forward can lead to overcounting.

Incorrect approach:

for left_index, (left_bound, right_bound) in enumerate(tiles):
    # ... expansion logic ...
  
    # Wrong: Forgetting to remove the current segment
    # current_coverage accumulates incorrectly

Why it fails: Without removing the leftmost segment, current_coverage keeps accumulating tiles that are no longer covered when the carpet moves to the next starting position, leading to incorrect maximum calculations.

Correct approach:

# Remove the current segment before moving to the next iteration
current_coverage -= right_bound - left_bound + 1

4. Assuming Carpet Must Start at a Tile Position

While the algorithm correctly starts the carpet at each segment's left boundary (which is optimal), a conceptual pitfall is thinking this is the only valid approach. The algorithm works because starting at any position between segments would cover fewer tiles than starting at the next segment's beginning.

Key insight: Starting the carpet at each segment's left boundary is sufficient to find the optimal solution - we don't need to check every possible integer position on the number line.