아직 계정이 없으신가요? 회원가입

관심 Tag

Talk 등록

Dev. Talk

강의실 배정 - 시간 초과 문제

회원사진robbinshs
137 views2023-02-16 00:08

강의실 배정문제에서 sort() <--- 시간 초과가 인하여 실패하는데


내용을 찾아보니 python에서는 heapq 모듈을 이용해서 구현하던데


js에서 heap 을 구현해서 작성해야 할까요? 


다른 방법은 없을까요?

const fs = require('fs');
const args = fs.readFileSync('/dev/stdin').toString().trim().split('
');

let [n, ...times] = args;
const arr = times.map(i=> i.split(' ').map(j=> +j));

arr.sort((a,b) => {
    if (a[1] === b[1]) return a[0] - b[0];
    else return a[1] - b[1];
})

let answer = 0;
let endPoint = 0;
for (let i=0; i<arr.length; i++) {
    if (endPoint <= arr[i][0]) {
        endPoint = arr[i][1];
        answer++;
    }
}

console.log(answer);