SRM645 Div1E

今日は娯楽をしすぎて(?)ぜんぜん精進できませんでした

 ・SRM645 Div1E JanuszTheBusinessman

あるホテルにn人の客が来る.i番目の客はarrivals[i]日目に来て,departures[i]日目に帰る.オーナーがサービスした客はレビューを書いてくれる.また,サービスした客と会った(同時に滞在している期間がある)客も同様にレビューを書いてくれる.オーナーは全ての客にレビューを書いてもらいたい.最小何人にサービスをすればよいか?という問題.

出来そうで出来なかった.こういう問題では区間を終端でソートすると良いことがありそうなのでソートしておく.まず最も早く帰る客に注目する.この客をカバーするには,この客またはこの客と会う客の誰かにサービスをする必要がある.よくかんがえると,そのような客の中で最も遅く帰る客にサービスをするのが最適であることがわかるので貪欲.なんかDPしようとしたり迷走した.

ソースコード

typedef pair<int,int> P;
class JanuszTheBusinessman {
    public:
    int makeGuestsReturn(vector<int> arrivals, vector<int> departures) {
        int n=arrivals.size();
        vector<P> v;
        for(int i=0;i<n;i++) v.emplace_back(departures[i],arrivals[i]);
        sort(v.begin(),v.end());
        bool vis[51]={};
        int ans=0;
        for(int i=0;i<n;i++) {
            if(vis[i]) continue;
            int mi=-1;
            for(int j=0;j<n;j++) {
                if(v[i].second>v[j].first||v[j].second>v[i].first) continue;
                if(mi==-1||v[mi].first<v[j].first) mi=j;
            }
            for(int j=0;j<n;j++) {
                if(v[mi].second>v[j].first||v[j].second>v[mi].first) continue;
                vis[j]=1;
            }
            ans++;
        }
        return ans;
    }
};