[백준 / JS ] 11000 강의실 배정

🕊 난이도

골드5

📣 풀이 방법

자바스크립트에서는 우선순위큐가 없기 때문에 최소 힙을 이용해서 풀었다.

1. 시작 시간으로 정렬한다.
   • 시작 시간이 같다면 끝나는 시간이 빠른 순서대로 정렬해준다.
2. 정렬된 배열을 순회한다.
   • 최소 힙에는 종료 시간만 넣어주면 된다.
   • 만약, 최소 힙에서 빠진 종료시간(i)보다 현재 위치에서의 종료시간(j)이 빠르다면, i를 다시 최소 힙에 넣어주고, j 또한 힙에 넣어준다.
   • 만약 같거나 크다면 j 만 넣어준다.
3. 최종적으로 최소 힙에 존재하는 size가 정답이다.

📄 전체 풀이

class minHeap {
  constructor() {
    this.heap = [];
    this.heap.push(-Infinity);
  }
  insert(val) {
    this.heap.push(val);
    this.upheap(this.heap.length - 1);
  }
  upheap(pos) {
    let tmp = this.heap[pos];
    while (tmp < this.heap[parseInt(pos / 2)]) {
      this.heap[pos] = this.heap[parseInt(pos / 2)];
      pos = parseInt(pos / 2);
    }
    this.heap[pos] = tmp;
  }
  get() {
    if (this.heap.length === 2) return this.heap.pop();
    let res = this.heap[1];
    this.heap[1] = this.heap.pop();
    this.downheap(1, this.heap.length - 1);
    return res;
  }
  downheap(pos, len) {
    let tmp = this.heap[pos],
      child;
    while (pos <= parseInt(len / 2)) {
      child = pos * 2;
      if (child < len && this.heap[child] > this.heap[child + 1]) child++;
      if (tmp <= this.heap[child]) break;
      this.heap[pos] = this.heap[child];
      pos = child;
    }
    this.heap[pos] = tmp;
  }
  size() {
    return this.heap.length - 1;
  }
  front() {
    return this.heap[1];
  }
}

const inputs = require("fs")
  .readFileSync(process.platform === "linux" ? "dev/stdin" : "input.txt")
  .toString()
  .trim()
  .split("\n");

const n = +inputs[0];
const lecture = [];

for (let i = 0; i < n; i++) {
  const l = inputs[i + 1].split(" ").map(Number);
  lecture.push(l);
}

lecture.sort((a, b) => (a[0] === b[0] ? a[1] - b[1] : a[0] - b[0]));

const mh = new minHeap();

mh.insert(lecture[0][1]);

for (let i = 1; i < n; i++) {
  const [start, finish] = lecture[i];

  const finishTime = mh.get();

  if (finishTime > start) {
    mh.insert(finishTime);
  }
  mh.insert(finish);
}

console.log(mh.size());