LeetCode 1094 - Car Pooling (Medium)

문제

LeetCode - 1094번

풀이 과정

문제 분류는 탐욕 알고리즘 이지만 입력 값의 범위가 크지 않기 때문에 브루트 포스 로도 충분히 해결할 수 있는 문제였습니다.

우리가 찾아야 하는 것은 한 시점에 필요한 최대 capacity 입니다.
따라서 시간을 0.5 단위로 증가시키며 겹치는 최대 구간을 찾도록 합니다.

이때 0.5씩 증가시켜준 이유는 거리가 1 단위이기 때문입니다.
(저와 같은 방법으로 구현한 분의 코드를 보니 시작 지점을 포함하고 종료 시간을 제외하여
1씩 증가시켜도 되도록 구현한 방법이 있었는데 그게 더 간단해보입니다.)

코드

/**
 * @param {number[][]} trips
 * @param {number} capacity
 * @return {boolean}
 */

var carPooling = function (trips, capacity) {
  let maxValue = 0;
  for (let time = 0.0; time <= 1000; time += 0.5) {
    let need = 0;
    for (let [c, s, e] of trips) {
      if (s < time && time < e) {
        need += c;
      }
    }
    maxValue = Math.max(maxValue, need);
  }

  return maxValue <= capacity;
};

const trips = [
  [3, 2, 7],
  [3, 7, 9],
  [8, 3, 9],
];
const capacity = 11;
console.log(carPooling(trips, capacity));