Maximum White Tiles Covered by a Carpet LeetCode solution in C++

1
class Solution {
2
 public:
3
  int maximumWhiteTiles(vector<vector<int>> &tiles, int carpetLen) {
4
    long long n = tiles.size(), ans = INT_MIN;
5
    sort(tiles.begin(), tiles.end());
6
    vector<long long> len(n), li(n);
7
    // len array stores the prefix sum of tiles
8
    // li array stores the last index tiles[i]
9
    for (int i = 0; i < n; i++) {
10
      len[i] = (long long)(tiles[i][1] - tiles[i][0] + 1);
11
      len[i] += (i == 0) ? 0 : len[i - 1];
12
      li[i] = tiles[i][1];
13
    }
14

15
    for (int i = 0; i < n; i++) {
16
      // sp means starting tile index
17
      // ep means ending tile index
18
      long long sp = tiles[i][0], ep = tiles[i][0] + (long long)carpetLen - 1, tc = 0;
19
      int idx = lower_bound(li.begin(), li.end(), ep) - li.begin();
20

21
      // logic to take count of tiles covered
22
      if (idx == n) {
23
        tc = len[n - 1];
24
        tc -= (i == 0) ? 0 : len[i - 1];
25
      } else {
26
        tc = ep < tiles[idx][0] ? 0 : ep - (long long)tiles[idx][0] + 1;
27
        idx--;
28
        if (idx >= 0) {
29
          tc += len[idx];
30
          tc -= (i == 0) ? 0 : len[i - 1];
31
        }
32
      }
33
      ans = max(ans, tc);
34
    }
35
    return (int)ans;
36
  }
37
};