Fast algorithm without implementing comparator<Interval>


  • 1
    A

    The idea is to sort the left ends and the right ends separately. Imagine the left ends are like left brackets, the right ends are like right brackets, sorted in a line. We just collect brackets in the ascending order. If the number of right brackets is equal to the number of left brackets, we get a maximal interval. Because sorting integer arrays are fast, this algorithm is under 20ms, beating 96%.

    public List<Interval> merge(List<Interval> intervals) {
            List<Interval> ans = new LinkedList<>();
            int l = intervals.size(), k = 0,  i = 0, j = 0, start = 0, end;
            int[] left = new int[l], right = new int[l];
            for (Interval interval : intervals) {
                left[k] = interval.start;
                right[k++] = interval.end;
            }
            Arrays.sort(left);
            Arrays.sort(right);
    // this while loop is like a merge sort, but simpler. We always have j<= i 
            while (i < l || j < l) {
                if (i == j && i < l) start = left[i++]; // start a new interval
                if (i < l && left[i] <= right[j]) i++;
                else {
                   end = right[j++];
                   if (j == i) ans.add(new Interval(start, end)); // If i == j, the current interval can not be extended
                }
            }
            return ans;
        }
    

  • 0
    B

    excellent solution!
    Can you please provide more detail about how you come up with this brilliant idea?


  • 0
    A

    I think I drew some pictures and found that merging intervals is like canceling brackets in the interior


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.