範例程式碼 uva10020

//uva10020
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

/**
* Why can I use greedy?
*
* ---------a-
* -----b-
*           ---x-
*     ---------------y-
* ===========cover=
*
* While I greedily choose `a', I still can choose `y' next round.
*/

class Segment {
public:
	int left, right;
	
	Segment(int l, int r) : left(l), right(r) {}
	
	bool operator <(const Segment &s) const {
		return left < s.left;
	}
};

int CoverIt(int m, vector<Segment> &seg, vector<Segment> &res) {
	Segment cover(0, m);
	sort(seg.begin(), seg.end()); // Sort by left edge.

	for (int i = 0; i < seg.size(); i) {
		/**
		* Each time,
		* among the segments that left edge is equal or smaller
		* than the left edge of the `cover',
		* choose the one whose right edge is the biggest.
		*
		* If the left edge of the first segment is not satisfied,
		* no one can satisfied anymore.
		* --> This case fail.
		*/
		if (seg[i].left <= cover.left); else return 0;
		Segment *max = &seg[i];
		for (i++; i < seg.size(); i++) {
			if (seg[i].left <= cover.left); else break;
			if (seg[i].right > max->right) max = &seg[i];
		}

		res.push_back(*max);
		cover.left = max -> right;
		if (cover.left >= cover.right) return res.size();
	}
	/**
	* If going through all the segments, the `cover' is still not covered,
	* this case also fail.
	*/
	return 0;
}

int main() {
	int n;
	scanf("%d", &n);
	while (n--) {
		int m;
		scanf("%d", &m);
		
		int l, r;
		vector<Segment> seg;
		while (scanf("%d%d", &l, &r) != EOF) {
			if (l == 0 && r == 0) break;
			seg.push_back(Segment(l, r));
		}
		
		vector<Segment> res;
		if (CoverIt(m, seg, res) > 0) {
			printf("%d\n", res.size());
			for (int i = 0; i < res.size(); i++) {
				printf("%d %d\n", res[i].left, res[i].right);
			}
		} else {
			printf("0\n");
		}
		
		if (n > 0) printf("\n");
	}
	return 0;
}