Maximum White Tiles Covered by a Carpet

For Maximum White Tiles Covered by a Carpet, the key observation is that an optimal carpet placement can be aligned to the start of some white interval. After sorting the non-overlapping tile ranges, evaluate each start position, use prefix sums to count fully covered intervals, and add at most one partially covered interval at the boundary. This turns a huge coordinate range into efficient interval math.

Problem Statement

You get several non-overlapping white tile intervals, where each pair [l, r] means every position from l through r is white. You may place one carpet of fixed length anywhere on the number line, and the carpet covers every position inside its span.

Your goal is to maximize how many white positions fall under that single carpet. The challenge in this problem is that coordinates can be as large as 10^9, so iterating position by position is impossible; the solution has to reason over interval boundaries and the few carpet placements that can actually be optimal.

Examples

Example 1

Input: tiles = [[1,5],[10,11],[12,18],[20,25],[30,32]], carpetLen = 10

Output: 9

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

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 Approach

1. Sort intervals and only test meaningful carpet starts

Because the intervals are non-overlapping, sort tiles by starting position. In an optimal solution, shifting the carpet left until its left edge hits the start of a white interval never hurts coverage, so it is enough to test carpet placements that start at tiles[i][0]. This removes the need to search the entire coordinate line.

2. Use prefix sums plus binary search to count full coverage fast

For each candidate start s = tiles[i][0], the carpet ends at e = s + carpetLen - 1. Binary search for the last interval whose start is at most e. Prefix sums over interval lengths let you count every fully covered interval between i and that boundary in O(1) after the search. This is the clean way to exploit the Array, Sorting, Prefix Sum, and Binary Search mix in problem 2271.

3. Add the boundary partial interval and keep the maximum

The last interval touched by the carpet may be only partially covered. After counting fully covered intervals, compute the overlap between [s, e] and that boundary interval, then subtract any uncovered suffix. Be careful not to double count when the first touched interval is itself partial. Track the best value over all starts, and return early if you ever reach carpetLen because no answer can exceed the carpet length.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

After sorting the intervals in O(n log n), each candidate start performs one binary search and O(1) prefix-sum arithmetic, so the total time is O(n log n). The extra space is O(n) for the sorted representation and prefix sums. A two-pointer version can reduce the repeated searches, but the binary-search formulation is often easier to explain cleanly in this exact problem.

What Interviewers Usually Probe

• You notice that the carpet never needs to start in the middle of empty space or inside a gap between intervals.
• You convert interval lengths into prefix sums so fully covered segments are added without re-walking them.
• You explicitly handle the final partially covered interval instead of assuming every touched interval is fully counted.

Common Pitfalls or Variants

Common pitfalls

• Trying to slide the carpet across every coordinate, which fails immediately because positions go up to 10^9.
• Double counting the last interval when binary search finds an interval that is only partially covered.
• Forgetting the inclusive endpoints, so overlap length should use end - start + 1 rather than end - start.

Follow-up variants

• Replace one carpet with two carpets; then the interval DP or split-point preprocessing becomes the main extension.
• Allow overlapping tile intervals; then you must merge intervals first before applying the same coverage logic.
• Ask for the exact carpet start position instead of only the count; store the best starting interval while computing the maximum.

FAQ

What is the main pattern in Maximum White Tiles Covered by a Carpet?

The practical pattern is sorted intervals plus targeted binary search over reachable coverage, not brute force over positions. You test carpet starts at tile boundaries, count fully covered intervals quickly, and then add one partial overlap at the edge.

Why can the carpet start be restricted to tile starts?

If a chosen carpet start lies inside a gap or inside an interval after its first white position, shifting it left to the nearest white interval start does not reduce covered white tiles. That means every optimal answer has an equivalent placement aligned to some tiles[i][0].

Is a sliding window also valid for problem 2271?

Yes. A two-pointer window over sorted intervals can maintain the total length of fully covered intervals and then compute the current partial overlap. It often achieves O(n) after sorting, while the binary-search version is slightly more direct to reason about from candidate starts.

Why do prefix sums help so much here?

Once intervals are sorted, prefix sums let you add the lengths of many fully covered intervals in constant time. Without them, each candidate carpet start would repeatedly sum the same interval lengths and turn an efficient solution into a slow one.

What is the easiest bug to make in this problem?

The most common bug is miscomputing the partial coverage of the last touched interval, especially with inclusive endpoints. Always compute overlap using max(left1, left2) and min(right1, right2), then add minRight - maxLeft + 1 only when that value is positive.