Solution

Approach #1 (Brute Force) [Accepted]

The straight-forward solution is to compare every two meetings in the array, and see if they conflict with each other (i.e. if they overlap). Two meetings overlap if one of them starts while the other is still taking place.

Java

public boolean canAttendMeetings(Interval[] intervals) {
    for (int i = 0; i < intervals.length; i++) {
        for (int j = i + 1; j < intervals.length; j++) {
            if (overlap(intervals[i], intervals[j])) return false;
        }
    }
    return true;
}

private boolean overlap(Interval i1, Interval i2) {
    return ((i1.start >= i2.start && i1.start < i2.end)
         || (i2.start >= i1.start && i2.start < i1.end));
}

Overlap Condition

The overlap condition in the code above can be written in a more concise way. Consider two non-overlapping meetings. The earlier meeting ends before the later meeting begins. Therefore, the minimum end time of the two meetings (which is the end time of the earlier meeting) is smaller than or equal the maximum start time of the two meetings (which is the start time of the later meeting).

Figure 1. Two non-overlapping intervals.

Figure 2. Two overlapping intervals.

So the condition can be rewritten as follows.

private boolean overlap(Interval i1, Interval i2) {
    return (Math.min(i1.end, i2.end) >
            Math.max(i1.start, i2.start));
}

Complexity Analysis

Because we have two check every meeting with every other meeting, the total run time is $$O(n^2)$$ . No additional space is used, so the space complexity is $$O(1)$$ .

Approach #2 (Sorting) [Accepted]

The idea here is to sort the meetings by starting time. Then, go through the meetings one by one and make sure that each meeting ends before the next one starts.

Java

public boolean canAttendMeetings(Interval[] intervals) {
    Arrays.sort(intervals, new Comparator<Interval>() {
        public int compare(Interval i1, Interval i2) {
            return i1.start - i2.start;
        }        
    });
    for (int i = 0; i < intervals.length - 1; i++) {
        if (intervals[i].end > intervals[i + 1].start) return false;
    }
    return true;
}

Complexity Analysis

• Time complexity : $$O(n \log n)$$ . The time complexity is dominated by sorting. Once the array has been sorted, only $$O(n)$$ time is taken to go through the array and determine if there is any overlap.

• Space complexity : $$O(1)$$ . Since no additional space is allocated.

Analysis written by: @noran