글 읽기 - 어떻게 해야 시간을 줄일 수 있을까요?

dmstjd10 3년 전 0

1. 2차원 배열로 입력받아 퀵정렬로 start값과 end값을 정렬시킨 후

2. while문으로 가장 작은 end값을 찾으면 count++하고

3. 그 다음번째 배열부터 다시 가장 작은 end값을 찾는 식으로 짰습니다.

시간초과가 나오는데 어떻게 해야 시간을 줄일 수 있을까요?

#include <stdio.h>
#include <limits.h>

static int cmprow(const void *a, const void *b)
{
    const int * const ia = a, * const ib = b;
    if(ia[0] < ib[0])
   		return -1;
   	else if(ia[0] > ib[0])
   		return 1;
   	else{
   		if(ia[1] < ib[1])
   			return -1;
		else if(ia[1] > ib[1])
			return 1;
		else
			return 0;	
	}
}

int main(){
	int N,i, j, count=0, start=0, min, index;
	int m[100001][2] = {0,};
	scanf("%d", &N);
	
	for(i=0; i<N; i++){
		scanf("%d %d", &m[i][0], &m[i][1]);
	}
	
	qsort(m,N,sizeof(*m),cmprow);
				
	i=0;
	while(1){
		if(m[i][0] >= start){
			min = INT_MAX;
			for(j=i; j<N; j++){
				if(min > m[j][1]){
					min = m[j][1];
					i = j;
				}
			}
			if(min == INT_MAX)
				break;
			count++;
			start = min;
		}
		i++;
	}
	
	printf("%d",count);
	return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

어떻게 해야 시간을 줄일 수 있을까요?

dmstjd10 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말