博文中会简要介绍Leetcode P0252题目分析及解题思路。

“Meeting Rooms”是一道比较简单的题目，但同时也是一道很经典的原型题。题目要求检查是否每个会议之间都没有重叠。基本思路是运用贪心算法来解决。

Given an array of meeting time intervals where intervals[i] = [starti, endi], determine if a person could attend all meetings.

Example 1:

Input: intervals = [[0,30],[5,10],[15,20]]
Output: false

为什么会想到贪心算法？

我们考虑任意多个会议，取两个紧密相邻的会议m1和m2来研究，即这两个会议之间不存在其他会议。不失一般性地，我们假设m1[0] < m2[0]（我们用m表示会议，m[0]表示会议开始时间，m[1]表示会议结束时间），那么如果这两个会议不重叠，那么显然有m2[0] > m1[1]，否则，两个会议出现重叠。

不难发现，如果根据会议开始时间由早到晚排序，由于m1和m2之间不存在其他会议，所以m2一定是紧跟m1之后发生的最近会议，那么如果m2与m1都没有出现重叠，那么显然m2之后发生的其他会议也不会与m1发生重叠。

为什么一定是按会议开始时间来排序呢？

要回答这个问题，我们可以再观察上述思路。我们在上述思路中选取的两个会议m1和m2是“紧密相邻的”，也就是m2是紧跟m1发生的会议。如果想要满足这个条件，我们势必要选取m1开始之后最早开始的会议，即m1[0]和m2[0]之间不应该存在其他会议的m[0]，于是这样的条件就自然地演变成按开始时间由早到晚排序。在这种排序方法下能确保上述思路中的选取条件。

以下是Java的题解代码实现。

class Solution {
    public boolean canAttendMeetings(int[][] intervals) {
        Arrays.sort(intervals, (x, y) -> {
            return (x[0]-y[0]);
        });
        
        int curr = 0, prev = 0;
        for (int[] interval: intervals) {
            curr = interval[0];
            if (curr < prev) {
                return false;
            }
            
            prev = Math.max(prev, interval[1]);
        }
        
        return true;
    }
}

以下是C++的题解代码实现。

class Solution {
public:
    bool canAttendMeetings(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end(), [](vector<int> x, vector<int> y) {
            if (x[0] <= y[0])
                return true;
            else 
                return false;
        });
        
        int prev = 0, curr = 0;
        for (vector<int> interval: intervals) {
            curr = interval[0];
            if (curr < prev) {
                return false;
            }
            
            prev = max(prev, interval[1]);
        }
        
        return true;
    }
};