[정올 2461] 공주님의 정원

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

JUNGOL

#include <stdio.h>

struct period {
	int start, end;
} flo[100010], tmp[100010];
int N, ans;

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

int main(void) {
	//3.1일부터 11.30일까지 꽃이 한가지 이상 피어 있도록 하는데 꽃의 수가 가장 적도록
	//freopen("input.txt", "r", stdin);
	scanf("%d", &N);
	int a1, a2, b1, b2;
	for (int i = 1; i <= N; i++) { 
		scanf("%d%d%d%d", &a1, &a2, &b1, &b2); 
		flo[i].start = a1 * 100 + a2;
		flo[i].end = b1 * 100 + b2;
	}
	mergesort(1, N); //시작시간->종료시간 으로 소팅
	int prevmax = 301, i = 1, nextmax = prevmax, maxi = 1, flag = 0;
	while (prevmax < 1201) {
		//s부터, p.eday까지 오는 날짜까지 돈 다음에, 가장 eday가 긴 날을 선정 -> 그 인덱스를 s로 선정 후 반복
		for (; i <= N; i++) {
			if (flo[i].start <= prevmax) {
				if (flo[i].end > nextmax) { //끝이 더 길어지는 경우 업데이트
					nextmax = flo[i].end;
					maxi = i;
				}
			}
			else break; //구간반복 끝
		}

		if (prevmax == nextmax) { //못 찾은 경우
			flag = -1;
			break;
		}
		else { //찾은 경우
			prevmax = nextmax;
			ans++;
		}
	}

	if (flag == -1) printf("0\n");
	else printf("%d\n", ans);

	return 0;
}