Cod sursa(job #2658191)

Utilizator cristi_macoveiMacovei Cristian cristi_macovei Data 13 octombrie 2020 13:39:00
Problema Subsecventa de suma maxima Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.65 kb
#include <fstream>
#include <algorithm>

using namespace std;

const int NMAX = 5e4;

bool comp(const pair<int, int>& p1, const pair<int, int>& p2) {
  return p1.second < p2.second || (p1.second == p2.second && p1.first < p2.first);
}

int n;
pair<int, int> a[NMAX];

int main() {
  ifstream in("int.in");
  ofstream out("int.out");

  in >> n;
  for (int i = 0; i < n; ++i)
    in >> a[i].first >> a[i].second;

  sort(a, a + n, comp);

  int cnt = 1, right = a[0].second;
  for (int i = 1; i < n; ++i) {
    if (a[i].first >= right) {
      ++cnt;
      right = a[i].second;
    }
  }

  out << cnt << '\n';

  return 0;
}