Merge Intervals - O(n) average case time rather than THETA(nlogn)

merge-intervals.js

// See: http://www.programcreek.com/2012/12/leetcode-merge-intervals/
console.log(mergeIntervals([[1,3],[2,6],[8,10],[15,18]]));
console.log(mergeIntervals([[1,8], [2,10], [3,6]]));
console.log(mergeIntervals([[1,8], [2, 8], [3, 6]]));

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

  var buckets = [], merged = [], iMap = new Map(), intervalIdx = 0;
  for (let i = 0, interval; interval = intervals[i]; i++) {
    let [lo, hi] = interval;
    if (!buckets[lo]) buckets[lo] = [];
    if (!buckets[hi]) buckets[hi] = [];
    buckets[lo].push(i);
    buckets[hi].push(i);
  }

  for (let i = 0; i < buckets.length; i++) {
    let intervals = buckets[i];
    if (intervals == null) continue;
    intervals.forEach(function(interval) {
      iMap.set(interval, (iMap.get(interval) || 0) + 1);
      if (!merged[intervalIdx]) merged[intervalIdx] = [i];
      if (iMap.get(interval) == 2) {
        iMap.delete(interval);
        if (iMap.size == 0) {
          merged[intervalIdx][1] = i;
          intervalIdx++;
        }
      }
    });
  }

  return merged;
}