[정올 1828] 냉장고

http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1101&sca=99&sfl=wr_hit&stx=1828 

JUNGOL

#include <stdio.h>

struct band {
	int min, max;
} C[105], Ans[105], tmp[105];
int Ccnt, Acnt;

void mergesort(int s, int e) {
	if (s >= e) return;
	int m = (s + e) / 2;
	mergesort(s, m);
	mergesort(m + 1, e);
	int k = s, a = s, b = m + 1;
	while (a <= m && b <= e) {
		if (C[a].min < C[b].min)		tmp[k++] = C[a++];
		else if (C[a].min > C[b].min)	tmp[k++] = C[b++];
		else
			if (C[a].max < C[b].max)	tmp[k++] = C[a++];
			else						tmp[k++] = C[b++];
	}
	while (a <= m) tmp[k++] = C[a++];
	while (b <= e) tmp[k++] = C[b++];
	for (int i = s; i <= e; i++) C[i] = tmp[i];
}

int main(void) {
	//freopen("input.txt", "r", stdin);
	scanf("%d", &Ccnt);
	for (int i = 0; i < Ccnt; i++) scanf("%d %d", &C[i].min, &C[i].max);
	mergesort(0, Ccnt - 1); //정렬
	Ans[Acnt++] = C[0];
	for (int i = 1, j = 0; i < Ccnt; i++) {
		for (j = 0; j < Acnt; j++) if ((C[i].min <= Ans[j].max && C[i].min >= Ans[j].min) || (C[i].max <= Ans[j].max && C[i].max >= Ans[j].min)) break; //겹치는게 하나라도 있는 경우
		if (j == Acnt) { //기존 범위에 넣지 못하면, 새로 만들어야 한다.
			Ans[Acnt++] = C[i];
		}
		else { //기존 범위에 넣을 수 있다면, 거기에 넣는다.
			if (Ans[j].min < C[i].min) Ans[j].min = C[i].min;
			if (Ans[j].max > C[i].max) Ans[j].max = C[i].max;
		}
	}
	printf("%d\n", Acnt);

	return 0;
}