「一本通 1.1 例 1」活动安排¶

Analysis¶

类似course schedule, $O(n\log(n))$

Code¶

/*
 * 活动安排.cpp
 * Copyright (C) 2020 Haoyang <[email protected]>
 *
 * Distributed under terms of the MIT license.
 */
#include <bits/stdc++.h>

using namespace std;

pair<int, int> arr[1010];
int main(int argc, char *argv[]) {
  int n;
  cin >> n;
  for (int i = 0; i < n; ++i) {
    cin >> arr[i].second >> arr[i].first;
  }
  sort(arr, arr + n);
  int start = -1, res = 0;
  for (int i = 0; i < n; ++i) {
    if (arr[i].second >= start) { // find new end time
      start = arr[i].first;
      ++res;
    }
  }
  cout << res;
  return 0;
}

Last update: January 9, 2021