以下のような貪欲なアルゴリズムを考えてみましょう。

満足できる温度の上限が最小である人を選び、その人の満足できる温度の上限の温度の温泉を用意する。その温泉で満足できる人をそれ以降考慮する人の集合から除く。

この操作を残っている人がいなくなるまで繰り返し、使用した温泉の個数を出力する。

実は、この貪欲なアルゴリズムは正しいです。この問題が区間スケジューリングと双対であることより示せます。

区間スケジューリングと双対であるとはこの問題の答えが同じ区間で区間スケジューリング問題を解いた時の最適解と同一になるという意味です。

まず、区間スケジューリング問題の解が \(k\) 個であったとすると、それらの区間は互いに交わらないのでそれらの区間にある温度の温泉を少なくとも \(k\) 個用意する必要がある。

逆に、 温泉を\(k\) 個用意するだけで十分であることは区間スケジューリング問題を解くアルゴリズムの動きから示せます。区間スケジューリング問題を解いた時に選んだ \(k\) 個の区間のそれぞれの一番高い温度を選択することで、\(k\) 個の温泉のみですべての区間をカバーできます。

また、先ほどの貪欲なアルゴリズムを実装する際は \(R_i\) の値の昇順でソートすることで簡潔に実装できます。

実装例(C++):

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<pair<int, int>> lr(n);
    for (int i = 0; i < n; i++) {
        cin >> lr[i].first >> lr[i].second;
    }
    sort(lr.begin(), lr.end(), [](pair<int, int> a, pair<int, int> b) {
        return a.second < b.second;
    });
    int now = -1;
    int ans = 0;
    for (int i = 0; i < n; ++i) {
        if (lr[i].first <= now && now <= lr[i].second) {
            continue;
        } else {
            now = lr[i].second;
            ans++;
        }
    }
    cout << ans << endl;
}