회의실 배정

한 개의 회의실이 있는데 이를 사용하고자 하는 n개의 회의들에 대하여 회의실 사용표를 만들려고 한다. 각 회의에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 최대수의 회의를 찾아라.

단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다.

▣ 입력설명

첫째 줄에 회의의 수 n(1<=n<=100,000)이 주어진다. 둘째 줄부터 n+1 줄까지 각 회의의 정
보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다.
회의의 시작시간과 끝나는 시간의 조건은 (시작시간 <= 끝나는 시간)입니다.

▣ 출력설명

첫째 줄에 최대 사용할 수 있는 회의 수를 출력하여라.

▣ 입력예제 1

5
1 4
2 3
3 5
4 6
5 7

▣ 출력예제 1

3

예제설명

(2, 3), (3, 5), (5, 7)이 회의실을 이용할 수 있다.

▣ 입력예제 2

3
3 3
1 3
2 3

▣ 출력예제 2

2

문제 풀이

그리디 알고리즘 문제이다. 여러가지 방법이 있으나, 회의 끝시간이 빠른 것들을 선택해야 더 많은 회의를 진행할 수 있다.

그리디 알고리즘(탐욕 알고리즘)

매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하는 알고리즘 설계 기법이다. 그러나 매 선택이 그 순간에 대해서는 최적이지만 그걸 종합적으로 봤을 때 최적이라는 보장은 절대 없다. 그래서 그리디 알고리즘은 부분의 최적해들의 집합이 곧 전체 문제의 해답이 될 때 사용한다.

회의 끝시간이 같은 회의가 여러개일 경우에는 시작시간 기준으로 오름차순 정렬을 해줘야한다. 만약 입력예제 2번처럼 시작시간=끝시간인 회의가 있다면 시작시간 빠른 것부터 세어주고 마지막으로 그 회의도 세어줘야 하기 때문이다.

1. 회의 끝시간이 같으면 시작시간 기준 오름차순 정렬
2. 회의 끝시간이 다르면 끝시간 기준 오름차순 정렬
3. 정렬된 배열 돌면서 시작시간이 끝시간과 같거나 그 뒤에 있다면 개수를 세어준다.
4. endTime을 현재 회의의 끝시간으로 설정한다.

function solution(array) {
  let answer = 0;
  array.sort((a, b) => {
    // 회의 끝이 같으면 회의 시작 기준으로 오름차순 정렬
    if (a[1] === b[1]) {
      return a[0] - b[0];
      // 아니면 회의 끝 기준으로 오름차순 정렬
    } else {
      return a[1] - b[1];
    }
  });

  let endTime = 0;
  for (let x of array) {
    if (x[0] >= endTime) {
      answer++;
      endTime = x[1];
    }
  }
  return answer;
}
let array = [
  [1, 4],
  [2, 3],
  [3, 5],
  [4, 6],
  [5, 7],
];
console.log(solution(array));