UnKoder #02 : Animal Party

ちょっと迷った。
https://www.hackerrank.com/contests/unkoder-02/challenges/animal-party

問題

N匹の犬とM匹の猫がいる。
それぞれを呼ぶと、[A[i],B[i])、[C[j],D[j])の時間帯(半開区間)にパーティーに参加する。

出来るだけ多くの動物をパーティーに呼びたいが、犬と猫が同じ時間帯にいないようにしたい。
最大何匹を呼ぶことができるか答えよ。

解法

区間スケジューリングの変形問題。
dp[犬の最後の登場時刻][猫の最後の登場時刻]=パーティーの参加動物数の最大値
で状態に対する動物数をDPを用いて更新していく。

全動物をパーティーの参加開始時間順に処理し、犬を追加する場合は猫の最後の登場時刻が犬の参加開始時刻以前である場合、猫の場合はその逆である状態に対して、1を加算していけばよい。

int N,M;
pair<int,int> P[101];
pair<int,int> Q[101];
int dp[103][103], ma;
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>P[i].first>>P[i].second, P[i].first++;
	cin>>M;
	FOR(i,M) cin>>Q[i].first>>Q[i].second, Q[i].first++;
	FOR(i,102) {
		FOR(j,N) if(P[j].first==i) {
			for(x=101;x>=0;x--) FOR(y,i) {
				dp[max(x,P[j].second)][y]=max(dp[max(x,P[j].second)][y],dp[x][y]+1);
				ma=max(ma,dp[max(x,P[j].second)][y]);
			}
		}
		FOR(j,M) if(Q[j].first==i) {
			FOR(x,i) for(y=101;y>=0;y--) {
				dp[x][max(y,Q[j].second)]=max(dp[x][max(y,Q[j].second)],dp[x][y]+1);
				ma=max(ma,dp[x][max(y,Q[j].second)]);
			}
		}
	}
	cout<<ma<<endl;
}

まとめ

UnKoderなのだから、題材はパーティーではなくトイレの占有時間とかにしても良かったのではないだろうか。