코딩 테스트 - [백준 1931] 회의실 배정(탐욕 알고리즘)

문제

한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

 

예제 입력

11
1 4
3 5
0 6
5 7
3 8
5 9
6 10
8 11
8 12
2 13
12 14

 

 

예제 출력

4

 

 

문제 해결 과정

 

이 문제는 회의가 끝나는 시간을 기준으로 배열을 정렬한다. 만약 끝나는 시간이 같은 것이 있다면 시작 시간이 빠른 시간 기준으로 정렬 한다.

 

 

나의 답안:

import Foundation

var num = Int(readLine()!)! //몇 개의 회의가 있는지 읽음

var numArr = [(Int, Int)]() // (Int,Int)로 구성된 빈 배열 선언 (2중 배열과는 좀 다른 느낌)
var count = 0 //최대 몇개의 회의가 가능한지 알려주는 변수
var now = -1 //현재 진행되고 있는 회의가 끝나는 시간

for i in 0..<num { //회의 시간들을 입력받고 numArr에 append
    var time = readLine()!.components(separatedBy: " ").map{Int(String($0))!}
    numArr.append((time[0],time[1])) //numArr에는 시작시간과 종료시간이 들어가게 됨

}

numArr.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 a in numArr { //정렬된 numArr
    if a.0 >= now { //현재 진행되고 있는 회의의 종료시간보다 다음 회의의 시작시간이 그 뒤면
        now = a.1 //종료시간을 다음 회의의 시간의 종료시간으로 변경 후
        count += 1 //카운트를 1 증가
    }
}
print(count)