题目描述

给定一系列的会议时间间隔，包括起始和结束时间[[s1,e1]，[s2,e2]，…(si < ei)，确定一个人是否可以参加所有会议。

样例1

输入: intervals = [(0,30),(5,10),(15,20)]
输出: false
解释:
(0,30), (5,10) 和 (0,30),(15,20) 这两对会议会冲突

样例2

输入: intervals = [(5,8),(9,15)]
输出: true
解释:
这两个时间段不会冲突

https://www.lintcode.com/problem/meeting-rooms/description

解法1

首先把时间段按照起始时间排序，如果存在任意的会议开始于前一个会议结束之前，则这个人无法参加所有回忆。我们将这种情况表示为，当∃ i ∈ [1, |intervals|)，使得intervals[i-1].end > intervals[i].start则无法参加所有会议，否则能够参加所有会议。还有一个特殊的case要处理，那就是没有会议时，我们应当将这种情况认定为能够参加所有会议。因为不能参加全部会议只有一个标准，就是下一个会议开始时，上一个会议没有结束；否则就应当认定为能够参加全部会议。

全部代码如下，时间复杂度O(nlogn)，空间复杂度O(1)。

import java.util.Comparator;
import java.util.List;

public class Solution {
    /**
     * @param intervals: an array of meeting time intervals
     * @return: if a person could attend all meetings
     */
    public boolean canAttendMeetings(List<Interval> intervals) {
        if (intervals == null || intervals.size() == 0)
            return true;
        intervals.sort(Comparator.comparingInt(a -> a.start));

        for (int i = 1; i < intervals.size(); i++) {
            Interval lastMeeting = intervals.get(i - 1);
            Interval currMeeting = intervals.get(i);
            if (currMeeting.start < lastMeeting.end)
                return false;
        }

        return true;
    }
}