题解 | #活动安排#

第一次写贪心，小记一下

#include <algorithm>
#include <iostream>
#include <utility>
#include <vector>

bool compare(std::pair<int, int> x1, std::pair<int, int> x2) {
  return x1.second < x2.second;
}

int main(int argc, char *argv[]) {
  int count = 0, size = 0, sum = 1;
  std::vector<std::pair<int, int>> activity_time;
  
  std::cin >> count;
  size = count - 1;
  
  while (--count >= 0) {
    int i, j;
    std::cin >> i >> j;
    activity_time.push_back({i, j});
  }
  
  std::sort(&activity_time[0], &activity_time[size+1], compare);  // 排序是左闭右开区间！！
  
  int cur_activity = activity_time[0].second;
  
  for (int i = 0; i < size; i++) {
    if (activity_time[i+1].first >= cur_activity) {
      sum++;
      cur_activity = activity_time[i+1].second;
    }
  }
  
  std::cout << sum << std::endl;
  
  return 0;
}