[75 LeetCode] 15 - Merge Intervals

[75 LeetCode]는 코딩테스트 연습을 위해 한 페이스북 개발자가 추천하는 75가지 알고리즘 문제를 풀어보는 시리즈이다.

블라인드 원문:
https://www.teamblind.com/post/New-Year-Gift---Curated-List-of-Top-75-LeetCode-Questions-to-Save-Your-Time-OaM1orEU

문제 링크: https://leetcode.com/problems/merge-intervals/

Merge Intervals - LeetCode

 

 

인터벌을 정렬 후 순회하게되면 현재 interval이 다음 interval과 연결된 경우 바로 연결해줄 수 있기 때문에 모든 노드에 대해 모든 노드를 순회할 필요가 없다. 
즉, O(n^2)의 탐색을 할 필요가 없다.

시간복잡도 O(n * logn)으로 해결할 수 있다. (정렬 = n * logn)

start와 end를 두고 intervals를 순회한다.

- end보다 현재 interval의 시작점이 작거나 같으면 두 인터벌은 합칠 수 있다. 즉, end를 max(end, 해당 인터벌의 끝 지점)으로 지정한다.

- 그렇지 않은경우, 현재의 start와 end는 이번 interval과 합쳐지지 않는다.
start와 end를 result 배열에 넣어준다.
그리고 새 start와 end를 지정해준다.

var merge = function(intervals) {
  intervals.sort((a,b) => (a[0] - b[0]));
  const res = [];
  let s = null;
  let e = null;

  
  for (let i = 0; i < intervals.length; i++) {
      // Null check 필요
      if (e !== null && e >= intervals[i][0]) {
          e = Math.max(intervals[i][1], e);
      } else {
          if (s !== null && e !== null) {
              res.push([s, e]);
          }
          s = intervals[i][0];
          e = intervals[i][1];
      }
  }

  if (s !== null && e !== null) {
      res.push([s, e]);
  }

  return res;
};

중간에 잠시 헤맸던게, `e !== null && e >= intervals[i][0]` 부분이었다.
첫 start와 end를 `null`, `null로` 놓고 진행한게 원인이었다.
end가 null일 때 `intervals[i][0]`가 0이면 `e >= intervals[i][0]`이 true가 된다.
(`(null >= 0) === true`)

부등호는 일치비교가 아닌 동등비교이기 때문이다. 숫자로 변경 후 비교하기 때문에 null -> 0 >= 0 -> true가 된다.

==이나 !=의 경우 주의하고 있기때문에 거의 사용하지 않는데, 부등식에서 함부로 null을 사용하면 안된다는 것을 다시 생각하게 됐다.