【leetcode】最多可以参加的会议数目

0、用到的相关知识

• Array.sort对数组排序，对对象数组排序，对二维数组排序。
• comparable、comparator 比较器接口实现
  (1. 匿名内部类 2、类实现接口)
• 创建二维数组
• 线程、线程代理类、sychornized锁对象
• 异常相关
• 优先级队列、堆、数组、树的顺序存储

一、题目描述

给你一个数组 events，其中 events[i] = [startDayi, endDayi] ，表示会议 i 开始于 startDayi ，结束于 endDayi 。

你可以在满足 startDayi <= d <= endDayi 中的任意一天 d 参加会议 i 。注意，一天只能参加一个会议。

请你返回你可以参加的 最大 会议数目。

输入：events = [[1,2],[2,3],[3,4]]
输出：3
解释：你可以参加所有的三个会议。
安排会议的一种方案如上图。
第 1 天参加第一个会议。
第 2 天参加第二个会议。
第 3 天参加第三个会议

二、 代码思想

首先，对会议开始时间进行排序，贪心的按照开始时间先后排序。

其次，选取已经开始的会议参加（因为我们尽可能贪心的先把开始的会议参加，没开始的会议不参加。

其次，在已经开始的会议里面我们选择，结束时间最早的会议参加。（这样也是贪心的思想，先把快结束的会议参加，防止到时候不能参加了，同时给后面的没结束的会议留出时间）；

最后，将已经结束的会议踢出去队列。

三、 代码题解

package leetcode;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

/*
 * @author lzy
 * @version 1.0
 * */
// Java创建二维数组 : https://blog.csdn.net/inexaustible/article/details/99240610
// Arrays.sort排序二维数组： https://blog.csdn.net/qq_44786115/article/details/104149433
// 线程相关： Sychornize锁的this是当前对象，当然也可以锁住当前对象的一些属性，静态方法上的Sychornize锁的是当前类，即类对象
// 线程代理类： 线程代理类做的工具就是将实现runnable接口的类注入，注入成为自己的属性，然后用start0创建线程调用其run方法
//           或者继承thread类的类重写run方法，此时并没有注入现runnable接口的类，所以此时调用的还是自己重写的run方法。
// 比较器相关：comparator接口，一般我们使用Arrays.sort/arrayList.sort方法时候，为了高效率我们仅仅传入一个匿名内部类对象(实现comparator接口)的
// 一般情况下我们要为类定义一个比较方法：compareTo 我们需要实现comparable接口，并创建类。
//这样一比较就体验到匿名内部类的优势，无需显示创建类，创建对象这样繁琐的工作，而是直接将对象作为参数传入即可。
// 异常相关： 运行时异常：数组越界、类型转换、算数异常等等 JVM自动帮我们处理
// 非运行异常：需要我们手动tyr catch 或者 抛给上一级函数来处理，如果大家都不处理最终抛给JVM来处理

public class Solution {
    public static void main(String[] args) {
        int array[][] = {{3,4},{2,3},{1,2},{1,2}};
        int res = maxEvents(array);
        for(int i = 0; i < array.length; i++) {
            System.out.println(array[i][0]);
        }
        System.out.println(res);
    }
    public static int maxEvents(int [][] events) {
        //可以通过Arrays.sort对二维数组进行排序
        //排序的规则就是以数组的某一个元素进行比较，来进行排序，排序之后，数组中的其他元素也跟着改变
        //详细解释一下： {【3，2】，【2，3】}，其中比较器中 01 是 【3，2】，02是 【2，3】 本质上，二维数组也就是一个个一维数组组成，所以二位数组的元素就是一维数组 01 -02
        //我们定义的比较规则是： 01【0】 与 02【0】 进行比较
        //Arrays.sort底层是使用快排的手段，将两个元素放入实现比较器：（Comparator接口）的匿名内部类中，然后按照比较规则对两个元素进行比较
        //最终得到排序后的数组
        Arrays.sort(events, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];
            }
        });
        //优先级队列： https://blog.csdn.net/BillieFan/article/details/107578057
        //优先级队列：就是一个队列，队头存放最小(最大元素)，可以添加对象，FIFO
        //其底层实现就是堆，堆的底层实现就是数组，数组用来存放数的顺序存储结构
        //调整堆的操作，也是通过数组来做的，因为数的顺序存储结构很特殊，知道i i*2 就是其孩子

        int res = 0;
        //表示当前第几个会议
        int curIndex = 0;
        //当前处于第几天
        int curDay = events[0][0];
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        while(curIndex < events.length || !pq.isEmpty()) {
            //加入已经开始的会议
            while(curIndex < events.length && events[curIndex][0] == curDay){
                pq.offer(events[curIndex][1]);
                curIndex++;
            }
            //剔除已经结束的会议
            while(!pq.isEmpty() && pq.peek() < curDay){
                //此时优先级队列的顶部存放的是结束时间最短的会议
                    pq.poll();
            }
            //找出结束时间最短的会议来参加
            while(!pq.isEmpty()) {
                pq.poll();
                res++;
                break;
            }
            curDay++;
        }
        //System.out.println(Arrays.toString(events));
        return res;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78