<p>You are given a 2D integer array <code>tiles</code> where <code>tiles[i] = [l<sub>i</sub>, r<sub>i</sub>]</code> represents that every tile <code>j</code> in the range <code>l<sub>i</sub> &lt;= j &lt;= r<sub>i</sub></code> is colored white.</p>

<p>You are also given an integer <code>carpetLen</code>, the length of a single carpet that can be placed <strong>anywhere</strong>.</p>

<p>Return <em>the <strong>maximum</strong> number of white tiles that can be covered by the carpet</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2022/03/25/example1drawio3.png" style="width: 644px; height: 158px;" />
<pre>
<strong>Input:</strong> tiles = [[1,5],[10,11],[12,18],[20,25],[30,32]], carpetLen = 10
<strong>Output:</strong> 9
<strong>Explanation:</strong> 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.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2022/03/24/example2drawio.png" style="width: 231px; height: 168px;" />
<pre>
<strong>Input:</strong> tiles = [[10,11],[1,1]], carpetLen = 2
<strong>Output:</strong> 2
<strong>Explanation:</strong> Place the carpet starting on tile 10. 
It covers 2 white tiles, so we return 2.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= tiles.length &lt;= 5 * 10<sup>4</sup></code></li>
	<li><code>tiles[i].length == 2</code></li>
	<li><code>1 &lt;= l<sub>i</sub> &lt;= r<sub>i</sub> &lt;= 10<sup>9</sup></code></li>
	<li><code>1 &lt;= carpetLen &lt;= 10<sup>9</sup></code></li>
	<li>The <code>tiles</code> are <strong>non-overlapping</strong>.</li>
</ul>

# tiles len N ~ 5 * 10^4. So time < O(N^2). sort the tiles by starting point. since no overlap, that's what we can have. l to r M ~ 10^9. Not even O(M)! Need to be faster, like O(logM) for any such search.
# start by placing carpet at the starting point at l1. there is no reason to place carpet before l1. We search for the range that is >= carpet end. So we can get the initial coverage.
# now think how we move the carpet. As we move towards the end of first tile r1, we always lose 1 in each step, but we don't necessarily get 1 in any new tile. So we definitely not going to get more. We can skip between [l1, r1]. Similarly, we can skip any [ln, rn].
# between [r1, l2], we may pick up new tiles. Note between [r1, l2], we don't lose any coverage between [l2, carpet end], but we may only pick up more tiles in the range. So we can directly jump to l2, because that's the maxim we could possible have!
# so we have: 1. between [ln, rn], coverage is <= coverage at ln; 2. between [rn, l(n+1)], the max coverage happens at l(n+1). So we only need to check coverage at each ln!
# to sum coverage at each ln: keep an index i of last li <= coverage. sum coverage during the move. for the next ln, roll index i forward. In this case, we only go over N tiles onece in O(N). We need to sort tiles in O(N * logN)
# wrong 1 (41 / 51 testcases passed): residual did not set up correct in code. Fix: add the correct residual


class Solution:
    def maximumWhiteTiles(self, tiles: List[List[int]], carpetLen: int) -> int:
        # sort tiles by start
        tiles.sort()
        #print(f"first tile: {tiles[0]}, last tile: {tiles[-1]}")
        # init at l0
        tile0 = tiles[0]
        carpet_end = tile0[0] + carpetLen
        ti_start = 0
        ti = 0
        cur_carpet = 0
        while ti < len(tiles) and tiles[ti][1] < carpet_end:
            tile_i = tiles[ti]
            cur_carpet += (tile_i[1] - tile_i[0] + 1)
            ti += 1
        # now ti is the first tile with tiles[ti][1] >= carpet_end, i.e. outside of carpet
        # add residual
        residual = 0
        if ti < len(tiles):
            tile_i1 = tiles[ti]
            if tile_i1[0] < carpet_end:
                residual = carpet_end - tile_i1[0]
                cur_carpet += residual
        #print(f"==init carpet start {tile0[0]}, end {carpet_end}, carpet {cur_carpet}, residual {residual}, first tiles {tiles[ti_start]}, last tile: {tiles[ti: (ti+1)]}")
        # early stop
        if cur_carpet == carpetLen: # max possible
            return carpetLen
        # iterate each l(n)
        max_carpet = cur_carpet
        while ti < len(tiles): # we have not cover all possible tiles yet, we can move to next ln
            # subtract last
            last_ti = ti
            tile_last = tiles[ti_start]
            cur_carpet -= (tile_last[1] - tile_last[0] + 1 + residual)
            residual = 0 # reset
            ti_start += 1
            carpet_end = tiles[ti_start][0] + carpetLen

            #print(f"==start i {ti_start}, carpet start {tiles[ti_start][0]} end {carpet_end}, cur carpet {cur_carpet}")

            while ti < len(tiles) and tiles[ti][1] < carpet_end:
                tile_i = tiles[ti]
                cur_carpet += (tile_i[1] - tile_i[0] + 1)
                ti += 1
            # add residual
            if ti < len(tiles):
                tile_i1 = tiles[ti]
                if tile_i1[0] < carpet_end:
                    residual = carpet_end - tile_i1[0]
                    cur_carpet += residual
            max_carpet = max(max_carpet, cur_carpet)

            #print(f"  final carpet {cur_carpet}, max_carpet {max_carpet}, residual {residual}, first tiles {tiles[ti_start]}, last tile: {tiles[ti: (ti+1)]}")

            if max_carpet == carpetLen: # max possible
                return carpetLen
        
        return max_carpet

815