1931번: 회의실 배정

그리디 문제의 특징

1. n이 제법 크다.
   → 이중 반복문 외의 프루탈 포스는 적용 불가능합니다.
2. 시간의 범위는 엄청 넓다.
   → [0] * n 등 메모리에 저장하는 방식은 불가능합니다.
3. 회의 시간이 주어지는 규칙은 없다
   → 규칙성 찾는 것 무의미합니다.

풀이

// 회의실

/*
 ❓ 한 회의실에서 최대한 많은 회의를 진행하기 위해서는 어떻게 해야할까?
 1. 진행해야 하는 회의 = 일찍 시작해서 일찍 끝나는 회의
 1. 기본적으로 일찍 끝나는 순서대로 회의를 진행해야한다.
    👉 일찍 끝나야 다음 회의가 또 들어갈 수 있으므로
 2. 끝나는 시간이 동일하다면 일찍 시작하는 회의 순서대로 진행한다.
    👉 사실 일반적인 경우 이 정렬은 큰 의미가 없지만 (어차피 끝나는 시간은 같으므로)
    👉 회의가 시작하자마자 끝나는 경우 (시작시간 = 끝시간)에는 끝나는 시간이 늘어나지 않고 회의를 +1할 수 있으므로 시작 순으로 정렬되어 있어야 한다.
 💡결론적으로 일찍 끝나는 순서대로 회의를 정렬하되 끝나는 시간이 같다면 일찍 시작하는 회의가 우선이 되어야 한다.
 */

typealias Meeting = (s: Int, e: Int)

let N = Int(readLine()!)!

var meetings = [Meeting]()

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

// 회의 정렬하기
meetings.sort { a, b in //💡 true면 a가 먼저, false면 b가 먼저
    if a.e == b.e { //👉 종료시간이 같다면
        return a.s < b.s // 시작 시간 순서대로
    } else {
        return a.e < b.e //👉 기본적으로 종료가 빠른 순서대로
    }
}

// 현재 진행 중인 회의가 끝나는 시간
var endTime = 0
// 진행할 수 있는 최대 회의의 갯수
var cnt = 0

for meeting in meetings {
    if meeting.s >= endTime { //👉 다음 회의를 진행할 수 있다면?
        cnt += 1 // 회의 갯수 추가
        endTime = meeting.e // 추가한 회의의 종료시간으로 갱신
    }
}

print(cnt)

1. 시작 시간과 끝나는 시간 중에 가장 우선적으로 고려할 것은 끝나는 시간입니다.
   1. 한 회의실에서 최대한 많은 회의를 해야하므로 빨리 앞 회의가 끝나야 다음 회의를 진행할 수 있습니다.
2. 그리고 나서 시작하는 시간을 고려합니다.
   1. 사실 끝나는 시간이 동일하다면 앞 회의가 끝난 후에 진행할 수 있는 아무 회의나 넣어도 상관 없습니다.
   2. ⭐️ 하지만 이 문제에는 시작 시간 = 종료 시간인 회의가 입력에 있습니다. 이런 회의는 넣을 수 있다면 무조건 넣어야 합니다.
   3. 따라서 종료 시간이 같다면 시작 시간 순으로 정렬해서 해당 회의가 추가될 수 있도록 합시다.

Swift의 Array 정렬하기

인자로 클로저를 받는 정렬 메소드는 2개의 인자를 (각각 a, b라고 합니다.) 가지고 있고 bool을 반환합니다.

이 경우 a가 먼저 와야한다면 true, b가 먼저 와야한다면 false를 반환하는 클로저를 전달하면 됩니다.

// 회의 정렬하기
meetings.sort { a, b in //💡 true면 a가 먼저, false면 b가 먼저
    if a.e == b.e { 
        return a.s < b.s 
    } else {
        return a.e < b.e
    }
}