5ms Java with sorting start and end point


  • 0
    H

    Although sort would disorder the start and end point pairs, but the idea is:
    After sorting, even if start point pair with a wrong end point, it doesn't matter.
    if largest end point large than next start point then renew largest end point as this start point paired end point.

    There are basically three situation:

    1. the original pair has no overlap with other pairs, so after sorting start point would be still paired with original end point, no effect from sorting
    2. the original pair has completely covered by another pair, so after sorting the small start point would paired with small end point, and large start point would paired with large end point, then we found the new end. Then this two pair would have same cumulative pair as no sorting.
    3. the original pair has some part overlapped by other, after sorting the smaller start point would also paired with old one.
    List<Interval> ret = new LinkedList<Interval>();
            int start[] = new int[intervals.size()];
            int end[] = new int[intervals.size()];
            for(int i = 0; i< intervals.size();i ++)
            {
                Interval tmp_in = intervals.get(i);
                    start[i] = tmp_in.start;
                    end[i] = tmp_in.end;
            }
            Arrays.sort(start);
            Arrays.sort(end);
            
            int k = 0;
            int tmp = 0;
            int i = 0;
            while(i < start.length)
            {
                tmp = end[i];
                int n = i;
                    while(true)
                    {
                        if(n < start.length && tmp >= start[n])
                        {
                            tmp = end[n];
                            n++;
                        }
                        else
                        {
                            ret.add(new Interval(start[i], tmp));
                            break;
                        }
                    }
                    i = n;
            }
            return ret;

Log in to reply
 

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