Maximum Sum Obtained of Any Permutation LeetCode solution in C++

1
class Solution {
2
 public:
3
  int MOD = 1e9 + 7;
4
  vector<int> createPermutation(vector<int> &nums, vector<vector<int>> &requests) {
5
    sort(begin(nums), end(nums));
6

7
    vector<int> sweep(nums.size() + 1);
8
    for (auto &x : requests) ++sweep[x[0]], --sweep[x[1] + 1];
9
    for (int i = 1; i < sweep.size(); ++i) sweep[i] += sweep[i - 1];
10

11
    vector<int> aux(nums.size());
12
    set<pair<int, int>> st;
13
    for (int i = 0; i < nums.size(); ++i) st.insert({sweep[i], i});
14

15
    int i = 0;
16
    while (st.size()) {
17
      auto [freq, idx] = *begin(st);
18
      st.erase(begin(st));
19
      aux[idx] = nums[i++];
20
    }
21
    return aux;
22
  }
23

24
  int maxSumRangeQuery(vector<int> &nums, vector<vector<int>> &requests) {
25
    vector<int> aux = createPermutation(nums, requests);
26
    vector<int> pref;
27
    for (auto &x : aux) pref.push_back(pref.empty() ? x : x + pref.back());
28
    int ans = 0;
29
    for (auto &x : requests)
30
      ans = (ans + (pref[x[1]] - (x[0] - 1 >= 0 ? pref[x[0] - 1] : 0) + MOD) % MOD) % MOD;
31
    return ans;
32
  }
33
};