CodeSprint Japan 40pt : 区間の選択

問題概要

重みなし区間スケジューリング問題を解く。ただし2個までは重複を許す。

解法

重み有り重複なしだとDPで重み有り重複有りだと最小費用流、重みなし重複なしだとGreedy、ここまでは知っていたけど重みなし重複ありは意外と知らなかった。制約見たらGreedyじゃないと厳しそうだったし、アルゴリズムデザインにGreedy使える問題として載っていたような気もしたので証明なしにそれっぽいのを書いたら通ってしまった。

acceptされたコード

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;

const int MAX_N = 1000;

struct range{
	int from, to;
	range(){}
	range(int from, int to):from(from), to(to){}
};

/*
bool operator< (const range& lhs, const range& rhs){
	return lhs.from != rhs.from ? lhs.from < rhs.from : lhs.to < rhs.to;
}
*/

bool operator< (const range& lhs, const range& rhs){
	return lhs.to != rhs.to ? lhs.to < rhs.to : lhs.from < rhs.from;
}


int N;
range rs[MAX_N];
int dp[2*MAX_N][4];
int buffer[2*MAX_N];
bool used[MAX_N];
vector<int> tars[2*MAX_N];

void init(){
	scanf("%d", &N);
	for(int i=0; i<N; ++i){
		int from, to;
		scanf("%d%d", &from, &to);
		rs[i] = range(from, to + 1);
	}
	for(int i=0; i<2*MAX_N; ++i){
		tars[i].clear();
	}
	memset(used, false, sizeof(used));
}

int solve(){
	int L = 0;
	for(int i=0; i<N; ++i){
		buffer[L++] = rs[i].from;
		buffer[L++] = rs[i].to;
	}
	sort(buffer, buffer + L);
	L = unique(buffer, buffer + L) - buffer;
	for(int i=0; i<N; ++i){
		rs[i].from = lower_bound(buffer, buffer + L, rs[i].from) - buffer;
		rs[i].to   = lower_bound(buffer, buffer + L, rs[i].to  ) - buffer;
	}

	sort(rs, rs + N);
	for(int i=0; i<N; ++i){
		tars[rs[i].from].push_back(rs[i].to);
	}

	int ans = 0;

	int r1 = 0, r2 = 0;
	for(int i=0; i<N; ++i){
		if(r1 <= rs[i].from){
			++ans;
			r1 = rs[i].to;
		}
		else if(r2 <= rs[i].from){
			++ans;
			r2 = rs[i].to;
		}

		if(r1 < r2){
			swap(r1, r2);
		}
	}

	return ans;

}

int main(){
	int T;
	scanf("%d", &T);
	for(int _=0; _<T; ++_){
		init();
		printf("%d\n", solve());
	}

	return 0;
}