Algorithm) BOJ) 백준 1931 - 회의실배정

문제보러가기

1. 초기접근

문제 조건 해석

어떻게 회의실을 최적으로 배정할 수 있을까?

배정하는 방법은 여러가지가 있다.

1. 시작 시간이 가장 빠른 회의부터 배정

가장 빨리 시작해서 가장 늦게 끝난다면..? 삐빅

2. 회의 시간이 가장 적은 회의부터 배정

그 사이에 앞뒤로 겹치는 회의가 많다면 효율적이지 못할 수 있다.

3. 끝나는 시간이 가장 빠른 회의부터 배정

이렇게 하면 배정했을 때 뒤에 남은 시간을 가장 최적으로 사용할 수 있게 된다.

 

알고리즘

끝나는 시간을 기준으로 정렬하고

배정한 뒤 끝나는 시간을 현재 시간으로 생각하고 다음 회의가 배정 가능한지 확인한다.

 

2. 회고

회의 시간이 가장 짧은 회의부터 배정하는게 최선인가 싶어 삽질을 많이 했었다. 이런 문제는 어떠한 상황이 가장 최적의 상황인지 경우의 수를 잘 나눠서 판단할 수 있어야겠다.

그리고 sorting할 때, 끝나는 시간으로만 정렬을 하면 틀리고 끝나는 시간이 같다면 시작 시간이 빠른 순서로 정렬을 해야 통과를 하는데… 왜그런지 정말 모르겠다. 아시는 분은 댓글로 남겨주시면 정말 감사하겠습니다… :D

3. 코드

guard let n = readLine().map({Int($0)!}) else {fatalError()}

var meetings = [(s: Int, e: Int)]()
var endTime = -1
var count = 0

for _ in 0..<n {
    guard let meet = readLine()?.split(separator: " ").map({Int($0)!}) else {fatalError()}
    
    meetings.append((s: meet[0], e: meet[1]))
}

// 끝나는 시간을 기준으로 정렬
meetings.sort {
    // 끝나는 시간이 같다면 시작 시간으로 정렬
    if $0.e == $1.e {
        return $0.s < $1.s
    } else {
        return $0.e < $1.e
    }
    
}

// 끝나는 시간이 가장 빠른 회의부터 for문
for m in meetings {
    // 현재시간(끝난시간)이 다음 회의의 시작시간보다 작거나 같다면
    if endTime <= m.s {
        count += 1
        endTime = m.e
    }
}

print(count)