1931번 - 회의실 배정
자꾸 시간 초과가 뜨길래 아래 greedy algorithm 구현한 부분을 바꿔줬더니 맞았습니다.
그런데 for문 두개 중첩으로 구현한 경우도 (주석처리한 부분) 일반적인 for문처럼 n*n 가지 경우를 계산하지 않고.. 아래 있는 for문이 위에 있는 for문의 i 를 바꿔주면서 실제로 시행한다면 O(n)시간이 걸릴 것 같습니다. 왜 시간 초과가 떴는지 모르겠습니다.
아래에 있는 for문이 i값을 바꾸는 경우는 mt[j].start >= mt[i].end 일 때 뿐입니다.
즉, n개의 모든 회의의 시작시간이 모든 회의의 끝나는 시간보다 작을 때는 해당 코드는 n^2을 돌게 됩니다.
댓글을 작성하려면 로그인해야 합니다.
jongh97 4년 전
자꾸 시간 초과가 뜨길래 아래 greedy algorithm 구현한 부분을 바꿔줬더니 맞았습니다.
그런데 for문 두개 중첩으로 구현한 경우도 (주석처리한 부분) 일반적인 for문처럼 n*n 가지 경우를 계산하지 않고.. 아래 있는 for문이 위에 있는 for문의 i 를 바꿔주면서 실제로 시행한다면 O(n)시간이 걸릴 것 같습니다. 왜 시간 초과가 떴는지 모르겠습니다.