1931

mergesort를 직접 구현해서 풀어보려고했는데 stack overflow문제가 계속 났었다.

나는 무한루프 때문인가 생각했는데 알고보니 함수 내에 지역변수를 너무 크게 잡은 메모리 초과가 원인이었다.

recursion 할 때 stack 메모리에 어떻게 쌓이는지 다시 한 번 복습하는 기분이었다.

해결방법은

지역변수를 크게 안잡고 전역 변수로 두면 된다. 어차피 한 번의 recursive한 함수가 한 번만 접근하니까. 여기서 여러개의 thread돌리는 것이 아니기 때문에 공유 문제는 걱정 안해도 된다.

 
#include<cstdio>

using namespace std;
struct course{
	int start, end;
};

course c[100005];
course tmp[100005];

int mySort(int start, int end){
	if(start==end)
		return 0;

	int mid = (start+end)/2;

	mySort(start, mid);
	mySort(mid+1, end);

	int piv_a=start, piv_b=mid+1;

	int cur=0;
	while(1){
		if(piv_a==mid+1 && piv_b == end+1)
			break;
		else if(piv_a==mid+1)
			tmp[cur++]=c[piv_b++];
		else if(piv_b==end+1)
			tmp[cur++]=c[piv_a++];
		else{
			if(c[piv_a].end < c[piv_b].end)
				tmp[cur++] = c[piv_a++];
			else if(c[piv_a].end > c[piv_b].end) 
				tmp[cur++] = c[piv_b++];
			else{
				if(c[piv_a].start < c[piv_b].start)
					tmp[cur++] = c[piv_a++];
				else
					tmp[cur++] = c[piv_b++];
			}
		}
	}

	for(int i=0; i<cur; i++)
		c[start+i]=tmp[i];
	
	return 0;
}


int main(){

	int n;
	scanf("%d", &n);

	for(int i=0; i<n; i++)
		scanf("%d %d", &c[i].start, &c[i].end);

	mySort(0, n-1);

	int cur_end = c[0].end;
	int res=1;

	for(int piv=1; piv<n; piv++){
		if(c[piv].start >= cur_end){
			res++;
			cur_end = c[piv].end;
		}
	}

	printf("%d\n", res);

	return 0;
}