Swift) 백준 11000번 강의실 배정 - G5

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

11000번: 강의실 배정

두개의 우선순위 큐를 이용해 풀었다.

 

첫번째 우선순위 큐는 배치할 수업의 우선순위. 

시작 시간이 가장 빠른 수업이 높은 우선순위를 가지고, 시작시간이 같은 경우 끝나는 시간 - 시작시간으로 수업의 길이가 가장 짧은 수업이 높은 우선순위를 가지게 한다.

 

두번쨰는 배치할 강의실의 우선순위.

배치할 강의의 우선순위는 끝나는 시간이 가장 짧은 강의실이 높은 우선순위를 가진다. 만약 peek를 한 강의실의 끝나는 시간이 배치할 수업보다 더 늦는다면, answer에 +1을 한 후 우선순위 큐에 해당 수업의 끝나는 시간으로 값을 입력한다.

 

처음에는 강의실을 배열로 짜서 for문으로 도는 방식으로 풀었지만, 최악의 경우 모든 강의가 시간이 안맞아서 강의실의 개수가 n이되면  시간복잡도가 O(n^2)이 되므로 시간초과가 뜬다. 현재 방식은 O(n)의 시간복잡도를 가지고 있다.

import Foundation

struct Heap<T: Comparable> {
    private var elements: [T]
    private var sortFunction: (T, T) -> Bool
    
    var isEmpty: Bool {
        return elements.isEmpty
    }
    
    var peek: T? {
        if self.isEmpty {
            return nil
        }
        return self.elements[0]
    }
    
    var count: Int {
        return elements.count
    }
    
    init(elements: [T], sortFunction: @escaping (T, T) -> Bool) {
        self.elements = elements
        self.sortFunction = sortFunction
        buildHeap()
    }
    
    private mutating func buildHeap() {
        for i in (0..<count/2).reversed() {
            siftDown(fromIndex: i)
        }
    }
    
    private mutating func siftDown(fromIndex index: Int) {
        var parentIndex = index
        while true {
            let leftChildIndex = 2 * parentIndex + 1
            let rightChildIndex = 2 * parentIndex + 2
            var highestPriorityIndex = parentIndex
            
            if leftChildIndex < count && sortFunction(elements[leftChildIndex], elements[highestPriorityIndex]) {
                highestPriorityIndex = leftChildIndex
            }
            
            if rightChildIndex < count && sortFunction(elements[rightChildIndex], elements[highestPriorityIndex]) {
                highestPriorityIndex = rightChildIndex
            }
            
            if highestPriorityIndex == parentIndex {
                break
            }
            elements.swapAt(parentIndex, highestPriorityIndex)
            parentIndex = highestPriorityIndex
        }
    }
    
    private mutating func siftUp(fromIndex index: Int) {
        var childIndex = index
        var parentIndex = (childIndex - 1) / 2
        while childIndex > 0 && sortFunction(elements[childIndex], elements[parentIndex]) {
            elements.swapAt(childIndex, parentIndex)
            childIndex = parentIndex
            parentIndex = (childIndex - 1) / 2
        }
    }
    
    mutating func insert(_ element: T) {
        elements.append(element)
        siftUp(fromIndex: count - 1)
    }
    
    mutating func pop() -> T? {
        guard !isEmpty else { return nil }
        elements.swapAt(0, count-1)
        let root = elements.removeLast()
        siftDown(fromIndex: 0)
        return root
    }
}

struct ClassModel: Comparable {
    
    let start: Int
    let finish: Int
    
    static func < (lhs: ClassModel, rhs: ClassModel) -> Bool {
        if lhs.start == rhs.start {
            return (lhs.finish - lhs.start) < (rhs.finish - rhs.start)
        }
        return lhs.start < rhs.start
    }
    
    
}

var classHeap = Heap<ClassModel>(elements: []) { $0 < $1 }
var classFinishHeap = Heap<Int>(elements: []) { $0 < $1 }
var answer = 0

let n = Int(readLine()!)!
for _ in 0..<n {
    let input = readLine()!.split(separator: " ").map{Int($0)!}
    classHeap.insert(.init(start: input[0], finish: input[1]))
}

for _ in 0..<classHeap.count {
    let popClass = classHeap.pop()!
    if classFinishHeap.isEmpty {
        answer += 1
        classFinishHeap.insert(popClass.finish)
        continue
    }
    let priorityClass = classFinishHeap.peek!
    if priorityClass <= popClass.start {
        classFinishHeap.pop()
        classFinishHeap.insert(popClass.finish)
    } else {
        answer += 1
        classFinishHeap.insert(popClass.finish)
    }
}

print(answer)