[코테] 회의실 배정

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

1931번: 회의실 배정

 

Greedy 문제 유형의 대표적인 문제 !! 회의실 배정을 풀었다.

 

우선 회의실을 끝나는 시간이 작은 순으로 정렬하고,

회의실을 순차적으로 살펴보면서 다음 회의실 예약 시작 시각이 현재 끝나는 시각보다 느리거나 같으면 카운트를 센다.

 

 

처음 제출한 답변

import Foundation

let n = Int(readLine()!)!
var meetings: [(s: Int, e: Int)] = []
for _ in 0..<n {
    let se = readLine()!.components(separatedBy: " ").map({ Int($0) ?? 0 })
    meetings.append((se[0], se[1]))
}
meetings = meetings.sorted(by: { $0.1 < $1.1 })

var cnt = 0, nowE = 0
for meeting in meetings {
    if meeting.s >= nowE {
        cnt += 1
        nowE = meeting.e
    }
}
print(cnt)

>> 틀렸습니다.

 

왜 틀렸을까 생각해봤는데 회의실 정렬 시, 끝나는 시각이 동일하면 시작시각이 빠른 순으로 정렬하는 것을 잊었다...

 

최종 답변

import Foundation

let n = Int(readLine()!)!
var meetings: [(s: Int, e: Int)] = []
for _ in 0..<n {
    let se = readLine()!.components(separatedBy: " ").map({ Int($0) ?? 0 })
    meetings.append((se[0], se[1]))
}
meetings = meetings.sorted { 
    if $0.1 == $1.1 {
        return $0.0 < $1.0
    } else {
        return $0.1 < $1.1
    }
}

var cnt = 0, nowE = 0
for meeting in meetings {
    if meeting.s >= nowE {
        cnt += 1
        nowE = meeting.e
    }
}
print(cnt)