jongh97   4년 전


자꾸 시간 초과가 뜨길래 아래 greedy algorithm 구현한 부분을 바꿔줬더니 맞았습니다.

그런데 for문 두개 중첩으로 구현한 경우도 (주석처리한 부분) 일반적인 for문처럼 n*n 가지 경우를 계산하지 않고.. 아래 있는 for문이 위에 있는 for문의 i 를 바꿔주면서 실제로 시행한다면 O(n)시간이 걸릴 것 같습니다. 왜 시간 초과가 떴는지 모르겠습니다.

pichulia   4년 전

아래에 있는 for문이 i값을 바꾸는 경우는 mt[j].start >= mt[i].end 일 때 뿐입니다.

즉, n개의 모든 회의의 시작시간이 모든 회의의 끝나는 시간보다 작을 때는 해당 코드는 n^2을 돌게 됩니다.

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