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

题解

暴力做法

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<i.end ，我们可以统计 0 到 j-1 最大的 end

排序+贪心

• 我们先按照左端点对会议时间间隔进行升序排序，如果左端点相同那么就按右端点升序排序
• 从左到右扫描一遍会议时间 并维护当前最大的结束时间 maxend，
• 如果 i.start<maxend 的话 因为已经排过序了，令 idx 的 end 是 maxend idx<i idx.start≤i.start<idx.end 证明两个时间间隔有交集，所以返回 false
• 有没有可能两个时间有交集，但不符合上面 i.start<maxend 的式子呢？ idx 和 i 时间有交集,即 idx.start≤i.start<idx.end A 式 没有交集,即 idx.start<idx.end≤i.start B 式 因为已经排过序了，所以 idx.start≤i.start 所以只要有一个 end 比 i.start 大就会发生交集，最容易比 i.start 大的 end 肯定是前面最大的一个 end 所以不会出现两个时间有交集，但不符合上面 i.start<maxend 的式子的情况 所以 i.start<maxend 这个式子是会议时间冲不冲突的充要条件

复杂度分析：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;     } } 

大佬有話說 (0)