[LeetCode] Merge Interval ( by using JavaScript )

문제

https://leetcode.com/explore/interview/card/top-interview-questions-medium/110/sorting-and-searching/803/

Explore - LeetCode

 

How to Solve ? 

 

처음에 아래와 같이 문제를 푸니까, 많은 예외처리에 실패를 했다.

결과적으로는 아래의 코드를 버리고, 검색을 하게 되었는데 정렬이 가능하다는 사실을 알게 되었고, 정답을 구할 수 있었다.

 

사실 정렬을 안되는 것처럼, 작성을 해놓은듯 하여 고생을 하기는 했지만,  문제를 풀 때 계속 막히는 기분이 든다면 가지고 있는 로직을 바탕으로 다시 설계 하는 것도 나쁘지 않겠다는 생각이 든다.

 

 

function solution(intervals) {
  for (let i = 0; i < intervals.length - 1; i++) {
    if (
      intervals[i][0] > intervals[i + 1][0] &&
      intervals[i][1] > intervals[i + 1][1]
    ) {
      let tmp = intervals[i];
      intervals[i] = intervals[i + 1];
      intervals[i + 1] = tmp;
    } else if (
      intervals[i][1] >= intervals[i + 1][0] ||
      intervals[i][1] >= intervals[i + 1]
    ) {
      if (intervals[i][1] <= intervals[i + 1][1]) {
        intervals[i][1] = intervals[i + 1][1];
      }

      if (intervals[i][0] > intervals[i + 1][0]) {
        intervals[i][0] = intervals[i + 1][0];
      }

      intervals.splice(i + 1, 1);
    }
  }
  return intervals;
}

정답 코드

 

function solution(intervals) {
  if (intervals.length < 2) return intervals;

  intervals.sort((a, b) => a[0] - b[0]);

  const result = [];
  let previous = intervals[0];

  for (let i = 1; i < intervals.length; i++) {
    
    if (previous[1] >= intervals[i][0]) {
      previous = [previous[0], Math.max(previous[1], intervals[i][1])];
    } 
    
    else {
      result.push(previous);
      previous = intervals[i];
    }
    
  }
  result.push(previous);

  return result;
}

let intervals = [
  [1, 3],
  [2, 6],
  [8, 10],
  [15, 18],
];
console.log(solution(intervals));