My Solutions
1. Count the coins of the bags either starting from the left end of every segment or ending with the right end of every segment2. Use the sliding window
**1. Count the coins of the bags either starting from the left end of every segment or ending with the right end of every segment**
```
/**
 * Time Complexity: O(n * log(n))
 * Space Complexity: O(n)
 * where `n` is the length of the vector `coins`
 */
class Solution {
 private:
  static constexpr int l_i = 0;
  static constexpr int r_i = 1;
  static constexpr int c_i = 2;

 public:
  long long maximumCoins(vector<vector<int>> &coins, const int k) {
    const int n = static_cast<int>(coins.size());
    sort(coins.begin(), coins.end());
    long long presums[n + 1];
    memset(presums, 0, sizeof(presums));
    for (int i = 0; i < n; ++i) {
      presums[i + 1] = presums[i] + count_coins(coins[i][l_i], coins[i][r_i], coins[i][c_i]);
    }

    long long ret = 0LL;
    for (int i = 0; i < n; ++i) {
      const int l = coins[i][l_i];
      const int r = coins[i][r_i];

      /**
       * count the coins from the bags starting from `l` and ending with `right`, both inclusive
       */
      const int right = l + k - 1;
      const int index_right = find_index(coins, right);
      const long long coins_at_index_right = count_coins(coins[index_right][l_i],
                                                         min(coins[index_right][r_i], right),
                                                         coins[index_right][c_i]);
      ret = max(ret, (presums[index_right] - presums[i]) + coins_at_index_right);

      /**
       * count the coins from the bags starting from `left` and ending with `r`, both inclusive
       */
      const int left = r - k + 1;
      const int index_left = find_index(coins, left);
      const long long coins_at_index_left = count_coins(max(coins[index_left][l_i], left),
                                                        coins[index_left][r_i],
                                                        coins[index_left][c_i]);
      ret = max(ret, (presums[i + 1] - presums[index_left + 1]) + coins_at_index_left);
    }
    return ret;
  }

 private:
  int find_index(const vector<vector<int>> &coins, const int coordinate) {
    int low = 0;
    int high = static_cast<int>(coins.size()) - 1;
    while (low < high) {
      const int mid = low + ((high - low) >> 1);

      if (coins[mid][l_i] <= coordinate && coordinate <= coins[mid][r_i]) {
        return mid;
      }

      if (coordinate > coins[mid][r_i]) {
        low = mid + 1;
      } else {
        high = mid;
      }
    }
    return high;
  }

  long long count_coins(const int l, const int r, const int c) {
    return static_cast<long long>(r - l + 1) * c;
  }
};
```
**2. Use the sliding window**
```
/**
 * Time Complexity: O(n * log(n))
 * Space Complexity: O(1)
 * where `n` is the length of the vector `coins`
 */
class Solution {
 private:
  static constexpr int l_i = 0;
  static constexpr int r_i = 1;
  static constexpr int c_i = 2;

 public:
  long long maximumCoins(vector<vector<int>> &coins, const int k) {
    sort(coins.begin(), coins.end());
    long long ret = count_coins(coins, k);
    reverse(coins);
    ret = max(ret, count_coins(coins, k));
    return ret;
  }

 private:
  long long count_coins(const vector<vector<int>> &coins, const int k) {
    const int n = static_cast<int>(coins.size());
    long long ret = 0LL;
    long long covered_coins = 0;
    for (int left = numeric_limits<int>::min(), i_left = 0, i_right = 0; i_right < n; ++i_right) {
      covered_coins += static_cast<long long>(coins[i_right][r_i] - coins[i_right][l_i] + 1) * coins[i_right][c_i];
      for (; coins[i_right][r_i] - coins[i_left][r_i] + 1 > k; ++i_left) {
        covered_coins -= static_cast<long long>(coins[i_left][r_i] - max(left, coins[i_left][l_i]) + 1) * coins[i_left][c_i];
      }
      left = max(left, coins[i_left][l_i]);
      const int next_left = coins[i_right][r_i] - k + 1;
      covered_coins -= static_cast<long long>(max(0, next_left - left)) * coins[i_left][c_i];
      left = next_left;
      ret = max(ret, covered_coins);
    }
    return ret;
  }

  void reverse(vector<vector<int>> &coins) {
    for (vector<int> &coin : coins) {
      swap(coin[l_i], coin[r_i]);
      coin[l_i] *= -1;
      coin[r_i] *= -1;
    }
    ::reverse(coins.begin(), coins.end());
  }
};
```
['C++']