1931 회의실 배정

Today 4/7

Greedy Algorithm

계산 속도가 빠르기 때문에 실용적이다.

항상 최적의 결과를 도출하는 것은 아니다.

탐욕 알고리즘이 성립하려면 두 가지 조건이 성립하여야 한다.

1. 탐욕스런 선택 조건(Greedy choice property) - 앞의 선택이 뒤의 선택에 영향을 주지 않는다.
2. 부분 구조 조건(optimal substructure) - 문제의 해가 부분문제에 대해서도 최적해이다.

회의실 배정 (My Code)

Greedy Algorithm으로 생각하면, 활동의 끝이 최대한 일찍 끝나는 쪽을 계속 고르면 된다.

var conferenceArr = [(Int, Int)]()
var startPoint = 0
var outputCount = 0

for _ in 0..<Int(readLine()!)! {
    let input = readLine()!.split(separator: " ").map{Int(String($0))!}
    let (start, end) = (input[0], input[1])
    conferenceArr.append((start,end))
}

conferenceArr.sort { (a: (Int,Int), b :(Int,Int)) -> Bool in
    if a.1 == b.1 {
        return a.0 < b.0
    } else {
        return a.1 < b.1
    }
}

for conference in conferenceArr {
    if conference.0 >= startPoint {
        startPoint = conference.1
        outputCount += 1
    }
}

print(outputCount)

sort에서 상세조건을 안넣어서 자꾸 틀렸다.

sort를 두 번 하는 이유는 시작시간과 끝나는 시간이 동일한 conference들이 있기 때문이다. ex) (10,10)

예를들어 (6,8), (10,10), (8,10) 과 (6,8), (8,10), (10,10)의 경우를 비교해보면 처음 경우는 2가 답인 반면, 뒤의 경우는 3이 답이 되어 sort에 따라 답이 다르게 나온다.

https://kau-algorithm.tistory.com/402