회의실 배정

회의실 배정

문제 설명

한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

예제 입력

11
1 4
3 5
0 6
5 7
3 8
5 9
6 10
8 11
8 12
2 13
12 14

예제 출력

4

---

문제 풀이

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

const solution = (input) => {
  const N = Number(input.shift());
  const rooms = input.map((line) => line.split(" ").map(Number));

  // start 기준 정렬
  rooms.sort((a, b) => {
    if (a[1] === b[1]) return a[0] - b[0]; // end 같으면 start 오름차순
    return a[1] - b[1]; // end 오름차순
  });

  let cnt = 0;
  // 가장 최소값
  let lastEnd = -Infinity;

  for (const [start, end] of rooms) {
    // 현재 시작할 수 있는 회의실의 시간과 그 전에 끝난 회의실의 시간과 같다면
    if (lastEnd <= start) {
      // 카운팅
      cnt++;
      // 끝난 회의실 재할당
      lastEnd = end;
    }
  }

  console.log(cnt);
};

solution(input);

아이디어 / 접근법

1. 우선 끝나는 시간으로 정렬 만약, 끝나는 시간이 같다면 시작시간으로 정렬
2. 끝나는 시간 기준으로 다음 회의실 찾기
3. 이전에 끝난 회의실의 시간이 현재 시작하는 시간보다 작다면 회의실을 대여할 수 있으므로 회의실을 빌리고 현재 회의실의 끝나는 시간을 재할당
4. cnt 출력

후기

그리디 중에서 가장 유명한 회의실 문제 였고 끝나는 시간으로 정렬을 할 수 있다면 크게 어려운 문제는 아니었다고 생각함. 끝나는 시간과 다음 회의실의 시작 시간을 비교해서 카운팅 해주고 끝나는 시간 바꿔주면 되는 문제