작성일 : January 19, 2022

문제 : https://www.acmicpc.net/problem/1931

해설 :

나의 풀이

/*
  11 [
  [ 1, 4 ],   [ 3, 5 ],
  [ 0, 6 ],   [ 5, 7 ],
  [ 3, 8 ],   [ 5, 9 ],
  [ 6, 10 ],  [ 8, 11 ],
  [ 8, 12 ],  [ 2, 13 ],
  [ 12, 14 ]
]
  */

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

let tmp = [];
let answer = 0;

for (let i = 0; i < arr.length; i++) {
  tmp.push(arr[i]);
  for (let j = i + 1; j < arr.length; j++) {
    const [start, end] = arr[j];

    if (tmp[tmp.length - 1][1] <= start) tmp.push([start, end]);
  }
  answer = Math.max(answer, tmp.length);
  tmp = [];
}

console.log(answer);

풀이 해설

정렬할때 끝시간이 같으면 시작시간 빠른게 앞에오도록

arr.sort((a, b) => (a[1] === b[1] ? a[0] - b[0] : a[1] - b[1]));
이런 방식으로 구현해야 맞았습니다 를 받을 수 있다 

후기

정답은 맞지만 시간 초과가 나서 O(n^2)을 피하고 싶은데 따로 아이디어가 생각나지 않았다..

시작시간 기준 정렬이 아닌 종료 시간 기준 정렬을 했어야 한다..... ㅂㄷㅂㄷㅂ