greedy

2021-06-30

贪心算法的使用证明最优子结构的解就是其中一个子问题额最优解,另外一个子问题为空。

// 1353. Maximum Number of Events That Can Be Attended
int maxEvents(vector<vector<int>>& events) {
  sort(begin(events), end(events));
  priority_queue<int, vector<int>, greater<int>> pq;
  int count = 0;
  int day = 0;
  int event_id = 0;
  while (event_id < events.size() || !pq.empty()) {
    if (pq.empty()) day = events[event_id][0];
    while (event_id < events.size() && events[event_id][0] <= day) {
      pq.push(events[event_id][1]);
      ++event_id;
    }
    while (!pq.empty() && pq.top() < day) {
      pq.pop();
    }
    if (!pq.empty()) {
      ++count;
      pq.pop();
    }
    ++day;
  }
  return count;
}

// 1754. Largest Merge Of Two Strings
string largestMerge(string word1, string word2) {
  if (!word1.size() || !word2.size())    
    return word1 + word2;
  if (word1 > word2) {
    return word1[0] + largestMerge(word1.substr(1), word2);
  } else {
    return word2[0] + largestMerge(word1, word2.substr(1));
  }
}

//