## 252. Meeting Rooms

Given an array of meeting time intervals consisting of start and end times `[[s1,e1],[s2,e2],...]` (si < ei), determine if a person could attend all meetings.

For example,
Given `[[0, 30],[5, 10],[15, 20]]`,
return `false`.

b'
\n\n

## Solution

\n
\n

#### Approach #1 (Brute Force) [Accepted]

\n

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.

\n

Java

\n
`public boolean canAttendMeetings(Interval[] intervals) {\n    for (int i = 0; i < intervals.length; i++) {\n        for (int j = i + 1; j < intervals.length; j++) {\n            if (overlap(intervals[i], intervals[j])) return false;\n        }\n    }\n    return true;\n}\n\nprivate boolean overlap(Interval i1, Interval i2) {\n    return ((i1.start >= i2.start && i1.start < i2.end)\n         || (i2.start >= i1.start && i2.start < i1.end));\n}\n`
\n

Overlap Condition

\n

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).

\n \n

Figure 1. Two non-overlapping intervals.

\n \n

Figure 2. Two overlapping intervals.

\n

So the condition can be rewritten as follows.

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

Complexity Analysis

\n

Because we have two check every meeting with every other meeting, the total run time is . No additional space is used, so the space complexity is .

\n
\n

#### Approach #2 (Sorting) [Accepted]

\n

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.

\n

Java

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

Complexity Analysis

\n
\n
• \n

Time complexity : .\nThe time complexity is dominated by sorting. Once the array has been sorted, only time is taken to go through the array and determine if there is any overlap.

\n
• \n
• \n

Space complexity : .\nSince no additional space is allocated.

\n
• \n
\n

Analysis written by: @noran

\n
'