public boolean canAttendMeetings(Interval[] intervals) {
if (intervals == null)
return false;
// Sort the intervals by start time
Arrays.sort(intervals, new Comparator<Interval>() {
public int compare(Interval a, Interval b) { return a.start  b.start; }
});
for (int i = 1; i < intervals.length; i++)
if (intervals[i].start < intervals[i  1].end)
return false;
return true;
}
AC clean Java solution


In the above implementation, you use the sort method to get all objects sorted  O(nlogn) time complexity.
After sorting you go through each object comparing it with the previous object to find if there is an overlap  O(n) time complexity.What if you can find if there is an overlap while you sort and raise a flag?
Here's my implementation:
private boolean canAttendMeetings(Interval[] intervals) { try { Arrays.sort(intervals, new IntervalComparator()); } catch (Exception e) { return false; } return true; } private class IntervalComparator implements Comparator<Interval> { @Override public int compare(Interval o1, Interval o2) { if (o1.start < o2.start && o1.end <= o2.start) return 1; else if (o1.start > o2.start && o1.start >= o2.end) return 1; throw new RuntimeException(); } }
While comparing two objects, if there is an overlap, it throws an Exception. The exception is caught during the run of the sort method is called. This avoids the extra search you require to go through the whole array to look for an overlap, if you don't mind making the comparison a little complex than the simple:
o1.start  o2.start

With lambdas in Java 8, you can actually write the comparator like this:
public boolean canAttendMeetings(Interval[] intervals) { // Sort the intervals by start time Arrays.sort(intervals, (x, y) > x.start  y.start); for (int i = 1; i < intervals.length; i++) if (intervals[i1].end > intervals[i].start) return false; return true; }

Sort by end times will also work in this problem. Here is my code doing the same :
public boolean canAttendMeetings(Interval[] intervals) { if (intervals.length == 0) return true; Arrays.sort(intervals, new Comparator<Interval>() { public int compare(Interval o1, Interval o2) { return o1.end  o2.end; } }); for (int i = 0; i < intervals.length  1; i++) { if (intervals[i + 1].start  intervals[i].end < 0) return false; } return true; }

@luan.gong Using Lambda hampers performance a lot, it might be using around 85 ms, without lambda it comes up to 12ms

@mithmatt
In java, throwing an exception is much more costly than return a boolean value.

@jackalsin What do you mean? That method must return an
int
. Also, the exception stops the whole algorithm, which is the point and should make it less costly (than finishing the sorting), no?What's the code you have in mind instead?