AC clean Java solution


  • 62
    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;
    }

  • 68
    M

    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


  • 2

    Interesting idea, though you might be replacing a cost of c1·n by a cost of c2·n·log(n)...


  • 1
    M

    @StefanPochmann

    Sorting and linear search: c1.nlogn + c2.n

    Sorting with throw error : c3.nlogn

    c1 < c3

    c2 < c3

    ?


  • 0

    I agree with your four statements but I don't see what your point/question is... :-)


  • 0
    M

    Just confirming whether my reasoning is right...


  • 27
    L

    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[i-1].end > intervals[i].start)
                return false;
        return true;
    }

  • 0

    Wow, this is awesome! Thank you so much for teaching me this beautiful technique! I am still a Java beginner :)


  • 3
    N

    You can use Integer.compare method to make it more in java 8 style e.g.
    Arrays.sort(intervals, (x, y) -> Integer.compare(x.start, y.start));


  • 0
    D

    In comparator, the first condition in both of the if statement is not necessary.


  • 0
    D

    agree with you, since the problem states that the input is start <= end.


  • 0
    P

    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;
    	}
    

  • 0
    This post is deleted!

  • 0
    A

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


  • 0

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


  • 0

    @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?


  • 0

    @StefanPochmann

    Sorry for the ambiguity.

    I agree what you commented. What I mean is that throwing an exception to set a flag is not quite acceptable. That solution is interesting, but really don't get the point.


Log in to reply
 

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