Skip to content

3413. Maximum Coins From K Consecutive Bags 👍

  • Time: $O(\texttt{sort})$
  • Space: $O(\texttt{sort})$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
class Solution {
 public:
  long long maximumCoins(vector<vector<int>>& coins, int k) {
    vector<vector<int>> negatedCoins = negateLeftRight(coins);
    return max(slide(coins, k), slide(negatedCoins, k));
  }

 private:
  vector<vector<int>> negateLeftRight(const vector<vector<int>> coins) {
    vector<vector<int>> res;
    for (const vector<int>& coin : coins) {
      const int l = coin[0];
      const int r = coin[1];
      const int c = coin[2];
      res.push_back({-r, -l, c});
    }
    return res;
  }

  long slide(vector<vector<int>>& coins, int k) {
    long res = 0;
    long windowSum = 0;
    int j = 0;

    ranges::sort(coins);

    for (const vector<int>& coin : coins) {
      const int li = coin[0];
      const int ri = coin[1];
      const int ci = coin[2];
      const int rightBoundary = li + k;

      // [lj, rj] is fully in [li..li + k)
      while (j + 1 < coins.size() && coins[j + 1][0] < rightBoundary) {
        const int lj = coins[j][0];
        const int rj = coins[j][1];
        const int cj = coins[j][2];
        windowSum += static_cast<long>(rj - lj + 1) * cj;
        ++j;
      }

      // [lj, rj] may be partially in [l..l + k)
      long last = 0;
      if (j < coins.size() && coins[j][0] < rightBoundary) {
        const int lj = coins[j][0];
        const int rj = coins[j][1];
        const int cj = coins[j][2];
        last = static_cast<long>(min(rightBoundary - 1, rj) - lj + 1) * cj;
      }

      res = max(res, windowSum + last);
      windowSum -= static_cast<long>(ri - li + 1) * ci;
    }

    return res;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
class Solution {
  public long maximumCoins(int[][] coins, int k) {
    int[][] negatedCoins = negateLeftRight(coins);
    return Math.max(slide(coins, k), slide(negatedCoins, k));
  }

  private int[][] negateLeftRight(int[][] coins) {
    int[][] res = new int[coins.length][3];
    for (int i = 0; i < coins.length; ++i) {
      final int l = coins[i][0];
      final int r = coins[i][1];
      final int c = coins[i][2];
      res[i][0] = -r;
      res[i][1] = -l;
      res[i][2] = c;
    }
    return res;
  }

  private long slide(int[][] coins, int k) {
    long res = 0;
    long windowSum = 0;
    int j = 0;

    Arrays.sort(coins, Comparator.comparingInt((int[] coin) -> coin[0]));

    for (int[] coin : coins) {
      final int li = coin[0];
      final int ri = coin[1];
      final int ci = coin[2];
      final int rightBoundary = li + k;

      // [lj, rj] is fully in [li..li + k).
      while (j + 1 < coins.length && coins[j + 1][0] < rightBoundary) {
        final int lj = coins[j][0];
        final int rj = coins[j][1];
        final int cj = coins[j][2];
        windowSum += (long) (rj - lj + 1) * cj;
        ++j;
      }

      // [lj, rj] may be partially in [l..l + k).
      long last = 0;
      if (j < coins.length && coins[j][0] < rightBoundary) {
        final int lj = coins[j][0];
        final int rj = coins[j][1];
        final int cj = coins[j][2];
        last = (long) (Math.min(rightBoundary - 1, rj) - lj + 1) * cj;
      }

      res = Math.max(res, windowSum + last);
      windowSum -= (long) (ri - li + 1) * ci;
    }

    return res;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution:
  def maximumCoins(self, coins: list[list[int]], k: int) -> int:
    return max(self._slide(coins, k),
               self._slide([[-r, -l, c] for l, r, c in coins], k))

  def _slide(self, coins: list[list[int]], k: int) -> int:
    coins.sort()
    res = 0
    windowSum = 0
    j = 0
    for li, ri, ci in coins:  # Consider the number line [li..li + k).
      rightBoundary = li + k

      # [lj, rj] is fully in [li..li + k).
      while j + 1 < len(coins) and coins[j + 1][0] < rightBoundary:
        lj, rj, cj = coins[j]
        windowSum += (rj - lj + 1) * cj
        j += 1

      # [lj, rj] may be partially in [l..l + k).
      last = 0
      if j < len(coins) and coins[j][0] < rightBoundary:
        lj, rj, cj = coins[j]
        last = (min(rightBoundary - 1, rj) - lj + 1) * cj

      res = max(res, windowSum + last)
      windowSum -= (ri - li + 1) * ci
    return res