[백준/Swift] 1931 : 회의실 배정

 

 

• BOJ_1931.swift

• 1931 : 회의실 배정/ 문제 소개
• 풀이 과정
• 코드 구현

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

1931번: 회의실 배정

1931 : 회의실 배정 / 문제 소개

 

회의실은 단 한개. N개의 회의 중 최대 개수를 찾는 문제이다.

N개의 회의가 있다. 

회의는 한번 시작하면 중단x.

회의가 끝나자 마자 다음 회의가 시작될 수 있다. 

회의 시작시간과 끝 시간이 같을 수 있다.

풀이 과정

 

Greedy문제로 이 문제를 풀었다.

간단하게 소개하자면

• 특정 순간에 당장 눈앞에 보이는 최적의 상황을 찾아 최종적인 해답에 도달하는 알고리즘

그리디 알고리즘을 어떻게 적용 시켜야 이 문제를 풀어 나갈 수 있을까?

 

1. 회의 시간 길이를 짧은 순으로 sort ? 후 선택? 
2. 시작 시간 빠른 회의 시간부터 선택?
3. 회의가 끝나자마자 시작하는강의 우선 선택?

회의를 선택하는 방법은 여러 가지가 있는데

1 의 경우에는 2시간의 짧은 회의시간 (시작, 끝) = (4,6) 이 있을 경우

(0,3 ) , (3,6) 3시간에 해당하는 두 회의를 선택하지 못한다.

2 의 경우 시작시간은 0 이지만 끝나는 시간이 1000000 이라면? 역시 최적의 선택이 아니다.

3 의 경우 (0,10) (10, 14) 이 두 회의가 있다면 연속적이라는 이유로 회의 시간을 선택해 버린다면 0~14 시간 중에 속한 회의들이 더 많이 존재할 수 있으므로 최적의 선택이 아니다.

 

답은 겹치지 않으면서 회의 끝나는 시간이 작은 회의 선택하는 것이다.

이 경우 뒤에 배정될 강의 개수가 많을 확율이 위에 언급된 여러 선택 방법보다 많다.

 

공부한 링크와 증명!!은 이 링크를 클릭하도 록~!! 아주 잘 설명해주신다.

 

문제를 풀며 주의해야 할 점은 회의실 끝나는 강의 정렬을 잘 해주어야 한다

코드 구현

 

import Foundation
typealias Element = (start: Int, end : Int)
// 이 문제는 소팅을 잘 해야한다.
func BOJ_1931()
{
    var n        = Int(readLine()!)!
    var selected = [Element]()
    var list     = [Element]()
    var index    = 0
    for _ in 0..<n
    {
        let se = readLine()!.split(separator: " ").map{Int(String($0))!}
        list.append((se[0],se[1]))
    }
    list.sort(by: )
    {
        if $0.end == $1.end
        {
            return $0.start < $1.start
        }
        return $0.end < $1.end

    }
    selected.append(list[0])
    for i in 1..<n
    {
        if selected[index].end <= list[i].start
        {
            selected.append(list[i])
            index += 1
        }
    }
    print(selected.count)
}
BOJ_1931()

 

visit my github