// Latihan bergaya OSN, Bab 12, soal 2 -- pembahasan. // // Urutkan menurut ujung kanan. Setiap kali ada selang yang belum // tertusuk, tempatkan titik di ujung kanannya -- posisi terjauh yang // masih sah, sehingga peluang menutupi selang berikutnya paling besar. #include #include #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector> selang(n); // (kanan, kiri) for (int i = 0; i < n; i++) { long long l, r; cin >> l >> r; selang[i] = {r, l}; } sort(selang.begin(), selang.end()); int banyak = 0; long long titik = -1; for (int i = 0; i < n; i++) { long long kanan = selang[i].first; long long kiri = selang[i].second; if (banyak == 0 || titik < kiri) { banyak++; titik = kanan; } } cout << banyak << "\n"; return 0; }