c언어 1931번 회의실 배정 (백준)

#include <stdio.h>

int main(void)
{
	long int n = 0;
	scanf("%ld", &n); //몇 개?
	
	long int a[n+1][2]; //시작시각, 종료시각 입력
	for(long int i = 0; i<n; i++) scanf("%ld %ld", &a[i][0], &a[i][1]);
	//shell sort 종료시각기준 오름차순 정렬
	long int i, j;
	long int key_1 = 0;
	long int key_2 = 0;
	long int gap = n/2;
	while(1)
	{
		if(gap%2==0) gap++;
		for(i = gap; i<n; i++)
		{
			key_1 = a[i][0];
			key_2 = a[i][1];
			for(j = i-gap; j>=0; j-=gap)
			{
				if(key_2 < a[j][1]) {
					a[j+gap][0] = a[j][0];
					a[j+gap][1] = a[j][1];
				} else break;
			}
			a[j+gap][0] = key_1;
			a[j+gap][1] = key_2;
		}
		if(gap==1) break;
		gap /= 2;
	}

	
	long int cnt = 0; //회의가 바뀐 횟수
    long int start = a[0][0]; //회의 시작한 시각
	long int end = a[0][1]; //회의 끝난 시각
	for(i = 1; i<n; i++)
	{
        if(end == a[i][1]) { //서로의 회의 끝난 시각이 같으며,
            if(!(a[i][1]-start)) { //기준보다 회의 시작 시간이 짧으면, 
            	cnt++; //회의 1번 바뀐 것으로 판단
            	if(start == a[i][0] && end == a[i][1]) cnt--; //그러나 시작시간도, 끝난시간도 같으면, 아래 조건과 중복되니 다시 제거 
            	start = a[i][0]; //기준 시작 시간을 더작은걸로 바꿈
			}
        }
        
        
		if(end <= a[i][0]) //회의 시작 시각이, 이전 회의 끝난 시각 보다 크거나 같다면
		{
			cnt++;
			end = a[i][1];
            start = a[i][0];
		} 
        
	}
	
	printf("%ld", cnt+1);
	//getch();
}

 

풀이

1) 종료 시각을 기준으로, 오름차순 정렬을 한다.
2) 같은 종료시각 내에서, 시작 시각을 기준으로, 오름차순 정렬을 한다.
3) 맨 처음 것의 종료시각을 기준으로, 이후의 시작 시각이 종료시각보다 크거나 같다면, +1 한 후, 이후의 종료시각을 기준으로 바꿔준다.
4) 출력

여기서 나는 1)을 했으나, 2)을 구현할 줄 몰라, 정렬 말고 다른 방식으로 만들었다.

ex) 3
2 2
0 2
1 2
3 4
의 이상적인 정렬은
0 2
1 2
2 2
3 4
이며, 여기서 답은
(0, 2) -> (2, 2) -> (3, 4) : 3 이다.
그러나 나는 시작 시각을 기준으로의 정렬을 구현하지 못했기에
시작 기준을 담는 변수를 만든 후,
서로의 종료 시각이 같을 때, 기준이 되는 회의 시작 시각과, 비교하는 회의의 종료 시각이 같으면, 횟수를 1 증가시키고, 시작 기준을 더 작은 걸로 바꿔 주었다. (단, 비교하는 두 회의의 시작 시각, 종료 시각 둘 다 같다면, 3) 절차에서 한 번 더 +1이 되므로, 모두 같을 경우엔 증가시켜서는 안 된다)

2 2 <- 기준
0 2
종료 시각 같으나, 시작 시각은 (0, 2)가 더 작으니 +1
시작 시각 기준도 2->0으로

0 2 <- 기준
1 2
종료시각 같으나, 시작 시각은 기준이 더 작으니 무시한다.

0 2 <- 기준
3 4
기준의 종료 시각보다 비교하는 것의 시작 시각이 더 크므로 +1
시작 기준은 3, 종료 기준은 4로 바뀐다.

https://www.acmicpc.net/problem/1931

1931번: 회의실 배정