HDU 2037 今年暑假不AC

题目链接：HDU 2037【今年暑假不AC】’

思路

       典型区间贪心，按节目结束时间升序排序，结束时间相等时按开始时间升序排序，然后逐个查找满足要求的节目，下一个观看的节目开始时间要大于当前观看节目的结束时间。

代码

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e5 + 10;
pair<ll, ll> p[N];
int n;
int main() {
  while (cin >> n) {
    if (n == 0)
      break;
    memset(p, 0, 0);
    for (int i = 1; i <= n; i++) {
      cin >> p[i].second >> p[i].first;
    }
    sort(p + 1, p + 1 + n);
    int num = 0;
    for (int i = 1; i <= n; i++) {
      int j = i;
      while (j <= n && p[j].second < p[i].first) {
        j++;
      }
      num++;
      i = j - 1;
    }
    cout << num  << endl;
  }
  return 0;
}