결혼식 - greedy(그리디)

풀이1 O(nlog(n))
주석 설명

// 결혼식 (그리디) -> On(logN)
function solution(times) {
  let answer = 0;
  let cnt = 0;
  let T_line = [];
  // start, end문자열과 함께 새로운 배열을 만든다
  for (const time of times) {
    T_line.push([time[0], 's']);
    T_line.push([time[1], 'e']);
  }
  // 첫번째 index기준으로 정렬을 하되 index0의 값이 같은경우는 해당문자를 unicode로 변환해서 정렬 (e가 s 보다 항상 먼저와야 정확한 계산이됨)
  T_line.sort((a, b) => {
    if (a[0] === b[0]) return a[1].charCodeAt(0) - b[1].charCodeAt(0);
    return a[0] - b[0];
  });
  // s일경우 더하고, e일경우빼면서 매반복마다 max값을 answer에 갱신해준다.
  for (const x of T_line) {
    if (x[1] === 's') cnt++;
    else cnt--;
    answer = Math.max(answer, cnt);
  }
  return answer;
}

console.log(
  solution([
    [14, 18],
    [12, 15],
    [15, 20],
    [20, 30],
    [5, 14],
  ])
);

풀이2 O(n2)
이중 for문 풀이

// 결혼식 (그리디) -> O(n2)
function solution(times) {
  let answer = 0;
  const sorted = times.sort((a, b) => {
    return a[0] - b[0];
  });
  for (let i = 0; i < sorted.length; i++) {
    let count = 1;
    for (let j = i + 1; j < sorted.length; j++) {
      if (sorted[i][1] > sorted[j][0] && sorted[i][1] < sorted[j][1]) {
        count++;
      }
    }
    answer = Math.max(answer, count);
  }
  return answer;
}

console.log(
  solution([
    [14, 18],
    [12, 15],
    [15, 20],
    [20, 30],
    [5, 14],
  ])
);