Maximum White Tiles Covered By A Carpet
01 · Problem
You are given a 2D array tiles where tiles[i] = [l_i, r_i] means every integer position from l_i to r_i (inclusive) is a white tile. The ranges do not overlap, but they are not necessarily given in sorted order. Every position not covered by a range is not white.
You also have one carpet that covers exactly carpetLen consecutive integer positions, and you may place it starting at any integer position.
Return the maximum number of white tiles the carpet can cover.
02 · Examples
tiles = [[2,6],[9,10],[14,20],[23,24]], carpetLen = 8
7
Place the carpet on positions 14 through 21. It covers the whole range 14-20, which is 7 white tiles. No other placement of length 8 covers more.
tiles = [[15,17],[3,4],[8,9]], carpetLen = 3
3
Placing the carpet on positions 15-17 covers 3 white tiles. The ranges are not necessarily given in sorted order.
tiles = [[2,4],[7,9]], carpetLen = 6
4
Positions 2-7 cover tiles 2, 3, 4 and 7, i.e. 4 white tiles. No placement of length 6 covers more, because the gap 5-6 always lies inside any window that touches both ranges.
03 · Constraints
- 011 <= tiles.length <= 5 * 104
- 02tiles[i].length == 2
- 031 <= l_i <= r_i <= 109
- 041 <= carpetLen <= 109
- 05The ranges in tiles are pairwise non-overlapping
04 · Optimal complexity
- Time
- O(n log n)
- Space
- O(n)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.