Комнаты для совещаний

Источник: https://leetcode.com/problems/meeting-rooms/

Дан массив интервалов, в которые проходят совещанияintervals, где intervals[i] = [starti, endi]. Определить, можно ли посетить все интервалы.

Пример 1:

Дано: intervals = [[0,30],[5,10],[15,20]]
Результат: false

Пример 2:

Дано: intervals = [[7,10],[2,4]]
Результат: true

Ограничения:

• 0 <= intervals.length <= 104
• intervals[i].length == 2
• 0 <= starti < endi <= 106

Идея решения

Фактически нам нужно отследить, перекрываются ли интервалы. Если перекрываются, что человек может присутствовать на одной встрече, а в это время начнется другая встреча.

Два интервала, например [start1, end1] и [start2, end2] перекрываются, когда  min(end1, end2)>max(start1, start2). min(end1, end2) - это завершение первого интервала, max(start1, start2) - это начало второго интервала. И если первый интервал завершается позже начала второго интервала, то у нас имеет место перекрытие интервалов.

Без ограничения общности мы можем отсортировать интервалы по точке старта. И тогда можно просто отканировать все интервалы, и проверить, соблюдено ли условие end1<start2. Если это не так, то второй интервал будет начинаться раньше, чем закончился первый. И человек не сможет посетить все совещания.

Имплеменатция

class Solution {
    public boolean canAttendMeetings(int[][] intervals) {
// сортируем по точке старта
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
// просматриваем все интервалы
        for (int i = 0; i < intervals.length - 1; i++) {
// intervals[i] - интервал, который стартовал раньше,
// его точка завершения intervals[i][1] должны быть <=intervals[i + 1][0]
            if (intervals[i][1] > intervals[i + 1][0]) {
                return false; // если это не так, то интервалы перекрываются
            }
        }
        return true; // мы просканировали весь список, не нашли аномалий, значит расписание ОК
    }
}