[백준] (Swift) 1931번 - 회의실 배정 (두번째 풀이) (feat. 그리디)

🟣 문제

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

1931번: 회의실 배정

 

🟣 나의 풀이 

끝나는 시간만 고려하면 되는줄알 고 정렬을 한번만 했다가 틀렸다. 음.. 그냥 일찍끝나면 좋겟지? 하하하하 하면서,, ? 단순하게, 어차피 끝나는 시간보다 시작시간이 작게 주어질테니, 끝나는 시간순서대로 정렬하면 시작순서는 어느정도 정렬이 될 줄 알았다.

틀리고 나서 다시 한번 생각해보니,,, '시작시간이 다르고 끝나는 시간이 같을 경우'를 생각하지 않았다. 만약 [2,3] 과 [3,3] 이 주어졌다면, 끝나는 시간순서대로만 정렬을 해버리면, 입력된 순서대로 [2,3] , [3,3]이 정렬될것이다. 하지만, 사실 [3,3]이 먼저 입력된 상황이라면, [3,3] 회의를 먼저 선택해버리게 되고, [2.3] 회의는 고려되지 못한다. (아래 예시)

❌ 끝나는 순서로만 정렬해서, 끝나는 시간이 같은 경우가 정렬되지 않았을 경우
meetings: [1, 1] [3, 3] [2, 3] 
[1, 1], [3, 3] 회의 선택 -> 답 2

✅ 시작순서도 정렬이 잘 되어있고, 끝나는 순서도 정리가 잘 되어있는 경우
meetings: [1, 1] [2, 3] [3, 3]
[1, 1] [2, 3] [3, 3] 회의 선택 -> 답 3

그래서 최대한 많은 회의를 선택하기 위해서는 끝나는 순서만 정렬하지 않고 시작순서까지 모두 정렬해주어야한다. 

이것만 해주고, 이전 회의 끝나는 시간을 고려해서 meetingCnt에 1씩 더해주면 끝!

🟣 정답코드

import Foundation

let n = Int(readLine()!)!
var meetings = [[Int]]()
for _ in 0..<n {
    meetings.append(readLine()!.split(separator: " ").map{ Int($0)! })
}
var meetingCnt = 0
var endTime = 0

meetings.sort{ return $0[0] < $1[0] }
meetings.sort{ return $0[1] < $1[1] }

for meeting in meetings {
    if meetingCnt == 0 || meeting[0] >= endTime {
        endTime = meeting[1]
        meetingCnt += 1
    }
}

print(meetingCnt)