贪心算法的使用证明最优子结构的解就是其中一个子问题额最优解,另外一个子问题为空。
// 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));
}
}
//
