Algorithm to Compute the Revenue Milestones

Revenue Milestones
X keeps track of the revenue X makes every day, and X wants to know on what days X hits certain revenue milestones. Given an array of the revenue on each day, and an array of milestones X wants to reach, return an array containing the days on which X reached every milestone.

1	int[] getMilestoneDays(int[] revenues, int[] milestones)

int[] getMilestoneDays(int[] revenues, int[] milestones)

Input
revenues is a length-N array representing how much revenue X made on each day (from day 1 to day N). milestones is a length-K array of total revenue milestones.

Output
Return a length-K array where K_i is the day on which X first had milestones[i] total revenue. If the milestone is never met, return -1.

Example
revenues = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100]
milestones = [100, 200, 500]
output = [4, 6, 10]

Explanation
On days 4, 5, and 6, X has total revenue of $100, $150, and $210 respectively. Day 6 is the first time that X has >= $200 of total revenue.

Using HashMap and Sorting to Compute the Revenue Milestones

The Milestones are not given in order. We can use a hash map to remember the indices and sort them. Then we can go through the revenue array and accumulate the total sum. Then we can use pointer to milestones to go through each milestone in ascending order, and reorder the day that achieve the milestone.

We have to use a while loop to iteratively check current total revenue is exceeding the current minimal milestone. The complexity is O(MN) where M is the number of days (size of revenue array) and N is the size of the milestones respectively.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

vector<int> getMilestoneDays(vector<int> revenues, vector<int> milestones) {
  vector<int> ans(milestones.size(), -1);
  // remember the milestone's indices
  unordered_map<int, int> idx;
  for (int i = 0; i < milestones.size(); ++ i) {
    idx[milestones[i]] = i;
  }
  sort(begin(milestones), end(milestones));
  int sum = 0;
  for (size_t i = 0, j = 0; j < revenues.size(); ++ j) {
    sum += revenues[j];
    // start from the current smallest milestone
    while ((i < milestones.size()) && (sum >= milestones[i])) {
      ans[idx[milestones[i]]] = j + 1;
      i ++;
    }
  }
  return ans;
}

vector<int> getMilestoneDays(vector<int> revenues, vector<int> milestones) {
  vector<int> ans(milestones.size(), -1);
  // remember the milestone's indices
  unordered_map<int, int> idx;
  for (int i = 0; i < milestones.size(); ++ i) {
    idx[milestones[i]] = i;
  }
  sort(begin(milestones), end(milestones));
  int sum = 0;
  for (size_t i = 0, j = 0; j < revenues.size(); ++ j) {
    sum += revenues[j];
    // start from the current smallest milestone
    while ((i < milestones.size()) && (sum >= milestones[i])) {
      ans[idx[milestones[i]]] = j + 1;
      i ++;
    }
  }
  return ans;
}

–EOF (The Ultimate Computing & Technology Blog) —