给定一系列的会议时间间隔，包括起始和结束时间[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
解释:
这两个时间段不会冲突

题解

1. 暴力做法
   for i in 1:n

   for  j  in 1:n
       判断i j有无交集
       判断方法，不妨令i.start<=j.start
       若
       i.start<=j.start<i.end 就会发生冲突
   

时间复杂度是O(N^2)从暴力出发，我们想该怎么优化
冲突的判断条件之一是i.start<=j.start
那我们可以先对时间间隔按照左端点升序方式进行排序，那么这个条件肯定是满足了
第二个条件j.start

1. 排序+贪心

• 我们先按照左端点对会议时间间隔进行升序排序，如果左端点相同那么就按右端点升序排序
• 从左到右扫描一遍会议时间 并维护当前最大的结束时间maxend，
• 如果i.start因为已经排过序了，令idx的end是maxend

idxidx.start≤i.start证明两个时间间隔有交集，所以返回false

• 有没有可能两个时间有交集，但不符合上面i.startidx和i时间有交集,即

idx.start≤i.start没有交集,即
idx.start因为已经排过序了，所以idx.start≤i.start
所以只要有一个end比i.start大就会发生交集，最容易比i.start大的end肯定是前面最大的一个end
所以不会出现两个时间有交集，但不符合上面i.start所以i.start

复杂度分析：N表示数组的长度

时间复杂度：取决于排序复杂度O(NlogN)，扫描的复杂度O(N)
空间复杂度：并没有多开辟空间，所以还是O(N)的
代码

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) {
        // Write your code here
        //按起点排序
        Collections.sort(intervals, new Comparator<Interval>() {
            public int compare(Interval x, Interval y) {
                return x.start - y.start;
            }
        });
        //维护最大的终点
        int maxend = -1;
        for(int i = 0; i < intervals.size(); i++) {
            if(intervals.get(i).start < maxend) {
                return false;
            }
            maxend = Math.max(maxend, intervals.get(i).end);
        }
        return true;
    }
}

更多题解参考：九章官网solution