391 · 数飞机  描述

给出飞机的起飞和降落时间的列表，用序列 interval 表示. 请计算出天上同时最多有多少架飞机？

如果多架飞机降落和起飞在同一时刻，我们认为降落有优先权。

样例

样例 1:

输入: [(1, 10), (2, 3), (5, 8), (4, 7)]
输出: 3
解释: 
第一架飞机在1时刻起飞, 10时刻降落.
第二架飞机在2时刻起飞, 3时刻降落.
第三架飞机在5时刻起飞, 8时刻降落.
第四架飞机在4时刻起飞, 7时刻降落.
在5时刻到6时刻之间, 天空中有三架飞机.

样例 2:

输入: [(1, 2), (2, 3), (3, 4)]
输出: 1
解释: 降落优先于起飞.

解法：
该图来自《古城算法》的视频，不是本人自己画的！贴在这里只是用于自己加强理解
 

/**
 * Definition of Interval:
 * public classs Interval {
 *     int start, end;
 *     Interval(int start, int end) {
 *         this.start = start;
 *         this.end = end;
 *     }
 * }
 */

public class Solution {
    /**
     * @param airplanes: An interval array
     * @return: Count of airplanes are in the sky.
     */
    public int countOfAirplanes(List<Interval> airplanes) {
        List<int[]> list  = new ArrayList();
        for(Interval pair:airplanes){
            list.add(new int[]{pair.start,1});//起飞的时候+1
            list.add(new int[]{pair.end,-1});//降落的时候-1
        }
        Collections.sort(list,(x,y)->{
            //此处确保降落(-1)排在起飞(1)之前
            if(x[0]==y[0]) return x[1]-y[1];
            return x[0]-y[0];
        });
        int count=0,max = 0;
        for(int[] pair:list){
            count += pair[1];
            max = Math.max(max,count);
        }
        return max;
    }
}

[LeetCode] 252. Meeting Rooms 会议室

Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), determine if a person could attend all meetings.

Example 1:

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

Example 2:

Input: [[7,10],[2,4]]
Output: true

/**
 * Definition of Interval:
 * public classs Interval {
 *     int start, end;
 *     Interval(int start, int end) {
 *         this.start = start;
 *         this.end = end;
 *     }
 * }
 */

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,(x,y)->{
            if(x.start==y.start) return x.end-y.end;
            return x.start-y.start;
        });
        for(int i=1;i<intervals.size();i++){
            Interval pre = intervals.get(i-1);
            Interval curr = intervals.get(i);
            if(curr.start<pre.end) return false;
        }
        return true;
    }
}

56. Merge Intervals

Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input. 

Example 1:

Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].

Example 2:

Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.

Constraints:

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

class Solution {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals,(x,y)->{
            if(x[0]==y[0]) return x[1]-y[1];
            return x[0]-y[0];
        });
        List<int[]> result = new ArrayList();
        for(int[] interval:intervals){
            if(result.isEmpty()) result.add(interval);
            else{
                int[] pre = result.get(result.size()-1);
                if(interval[0]<=pre[1])
                    pre[1] = Math.max(pre[1],interval[1]);
                else
                    result.add(interval);
            }
        }
        int[][] arr = new int[result.size()][2];
        for(int i=0;i<result.size();i++) arr[i]=result.get(i);
        return arr;
    }
}

 

919 · Meeting Rooms II Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), find the minimum number of conference rooms required. Example1

Input: intervals = [(0,30),(5,10),(15,20)]
Output: 2
Explanation:
We need two meeting rooms
room1: (0,30)
room2: (5,10),(15,20)

Example2

Input: intervals = [(2,7)]
Output: 1
Explanation: 
Only need one meeting room

 第一种解法：数飞机

/**
 * Definition of Interval:
 * public classs Interval {
 *     int start, end;
 *     Interval(int start, int end) {
 *         this.start = start;
 *         this.end = end;
 *     }
 * }
 */

public class Solution {
    /**
     * @param intervals: an array of meeting time intervals
     * @return: the minimum number of conference rooms required
     */
    public int minMeetingRooms(List<Interval> intervals) {
        List<int[]> list = new ArrayList();
        for(Interval pair:intervals){
            list.add(new int[]{pair.start,1});
            list.add(new int[]{pair.end,-1});
        }
        Collections.sort(list,(x,y)->{
            if(x[0]!=y[0]) return x[0]-y[0];
            return x[1]-y[1];
        });
        int result = 0;
        int count = 0;
        for(int[] pair:list) {
            count+=pair[1];
            result=Math.max(result,count);
        }
        return result;
    }
}

第二种解法：