この問題は貪欲法で解くことができます。

問題の条件は各バスに乗る人の希望出発時刻の最大値と最小値の差が \(K\) 以下と言い換えられます。つまり、最小値を固定すると、バスに乗れる人の集合が定まります。これを最小値から順に決定していく貪欲法を行います。

具体的には、希望出発時刻で昇順に並べ替えて、最も時刻が早い人からバスに乗せて行き、乗せられる限り同じバスに割り当てていくというのを繰り返します。

ソートがボトルネックとなり時間計算量は \(\mathrm{O}(N\log N)\) となります。

実装例(C++)

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, k;
    cin >> n >> k;
    vector<int> t(n);
    for (auto& e : t) cin >> e;
    int lst = -1;
    int ans = 0;
    sort(t.begin(), t.end());
    for (auto e : t) {
        if (lst < e) {
            ans++;
            lst = e + k;
        }
    }
    cout << ans << endl;
}