SRM 645 div1 easy:JanuszTheBusinessman

こういうの苦手。

問題:TopCoder Statistics - Problem Statement

解法:departure順に客をソートする。で,ある客がまだ処理済み出ない時,その客を処理できる中で最もdepartureするのが遅い客を選択する。この選び方で最適なのは帰納法的に証明できる(と思う)。直感的にはdepartureするのが早い人をカバーしながらdepartureがなるべく遅くなるように引っ張ってくるからですかね。ちょっと蟻本とか読んで復習してみます・・・
以下ソースコード

struct visit {
    int a;
    int d;
    visit(int a, int d) : a(a), d(d) {}
    visit() {}
    bool operator<(const visit& rhs) const {
        if (d != rhs.d) return d < rhs.d;
        return a < rhs.a;
    }
};

class JanuszTheBusinessman {
public:
    int makeGuestsReturn(vector <int> arrivals, vector <int> departures) {
        int n = arrivals.size();
        vector<visit> V(n);
        for (int i = 0; i < n; i++) V[i] = visit(arrivals[i], departures[i]);
        sort(V.begin(), V.end());
        int ret = 0;
        for (int i = 0; i < n; i++) {
            int last = i;
            for (int j = i; j < n; j++) {
                if (V[j].a <= V[i].d) last = j;
            }
            ret++;
            for (i = last; i < n; i++) {
                if (V[last].d >= V[i].a) continue;
                else break;
            }
            i--;
        }
        return ret;
    }
};