[정올 2247] 도서관

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

JUNGOL

#include <stdio.h>

struct time {
	int min, max;
} stdt[10010], sol[10010], tmp[10010];
int N, solnum, longtime, emptytime;

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

	for (int i = s; i <= e; i++) stdt[i] = tmp[i];
}

int main(void) {
	//freopen("input.txt", "r", stdin);
	scanf("%d", &N);
	for (int i = 0; i < N; i++) scanf("%d%d", &stdt[i].min, &stdt[i].max);
	mergesort(0, N - 1);

	//겹치는건 다 하나로 합치고 비교하자
	sol[0] = stdt[0];
	for (int i = 1; i < N; i++) {
		int& curmax = sol[solnum].max;
		if (stdt[i].min > curmax) { //겹침이 끝나는 경우
			if (emptytime < stdt[i].min - curmax) emptytime = stdt[i].min - curmax; //빈 시간 업데이트
			if (longtime < curmax - sol[solnum].min) longtime = curmax - sol[solnum].min; //긴 시간 업데이트
			sol[++solnum] = stdt[i];
		}
		else if (curmax < stdt[i].max) curmax = stdt[i].max; //겹치는데 길어지는 경우
	}
	if (longtime < sol[solnum].max - sol[solnum].min) longtime = sol[solnum].max - sol[solnum].min; //긴 시간 업데이트

	printf("%d %d\n", longtime, emptytime);

	return 0;
}