Beat 98% Java. Sort start & end respectively.


  • 67
    D

    The idea is that for the result distinct Interval, the latter one's start must > previous one's end.

    public List<Interval> merge(List<Interval> intervals) {
    	// sort start&end
    	int n = intervals.size();
    	int[] starts = new int[n];
    	int[] ends = new int[n];
    	for (int i = 0; i < n; i++) {
    		starts[i] = intervals.get(i).start;
    		ends[i] = intervals.get(i).end;
    	}
    	Arrays.sort(starts);
    	Arrays.sort(ends);
    	// loop through
    	List<Interval> res = new ArrayList<Interval>();
    	for (int i = 0, j = 0; i < n; i++) { // j is start of interval.
    		if (i == n - 1 || starts[i + 1] > ends[i]) {
    			res.add(new Interval(starts[j], ends[i]));
    			j = i + 1;
    		}
    	}
    	return res;
    }

  • 1
    C

    @D_shaw Good idea!


  • 0
    S

    Brilliant! ~~~


  • 0
    S

    brilliant solution!


  • 4
    T

    Can someone explain to me why this approach is faster than just by sorting the start time itself? Shouldn't this approach be slower because you have to sort 2 arrays and loop through the intervals two times?


  • 0
    S
    This post is deleted!

  • 0
    T

    @shamanthnorway Well, I'm talking about this solution comparing with here (solving by just sorting the start time). The time complexity for these 2 solutions should be the same O(n log n) since using Collections.sort() with a Comparator will take O(n log n), not O(n^2).

    However, for this current approach (sorting both start and end), it should be slower for small test cases in my opinion because you have to sort both arrays and loop through the intervals 2 times (1 for populating the arrays, 1 for getting the result)


  • 2
    K

    @timmy2702 Number of operations is not everything. If this solution takes more operations but each one takes less time than the simple solution, it could end up faster. I doubt the OP knew it would be faster until they tested it.


  • 0
    S

    Brilliant!!!!


  • 2
    B

    @Kelicious I think it's also possible that it's quicker to sort array of primitives like integers, rather than array of objects.


  • 0
    E

    This is a really brilliant way of solving this problem.


Log in to reply
 

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