题目
题目链接：
https://www.nowcoder.com/practice/4d3151698e33454f98bce1284e553651
https://leetcode.cn/problems/maximum-number-of-events-that-can-be-attended/description/
思路
贪心+优先级队列
Java代码
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param meetings int整型ArrayList<ArrayList<>>
* @return int整型
*/
public int attendmeetings (ArrayList<ArrayList<Integer>> meetings) {
//贪心+优先级队列
//力扣1353. 最多可以参加的会议数目 力扣上题目描述的更好
int ans = 0, max = -1; //max为最后一个会议的结束时间
//按会议结束时间排序
PriorityQueue<Integer> q = new PriorityQueue<>(new Comparator<Integer>() {
@Override
public int compare(Integer a, Integer b) {
return a - b;
}
});
// key -> 第 i 天, value -> 第 i 天开始的会议的结束时间
Map<Integer, List<Integer>> map = new HashMap<>();
for (ArrayList<Integer> e : meetings) {
//将开始时间相同的所有会议的结束时间放一起
if (!map.containsKey(e.get(0))) {
map.put(e.get(0), new ArrayList<>());
}
map.get(e.get(0)).add(e.get(1));
//max为最后一个会议的会议结束时间
max = Math.max(e.get(1), max);
}
// 整体思路就是从1开始到最晚结束时间依次遍历一遍，然后挑选此时间要进行的会议；
// 而队列的作用就是存储未进行的会议；挑选的判断条件就是挑选的时间不能小于此时的时间，
// 因为队列中存储的是每个会议最晚进行时间，即，结束时间
for (int i = 1; i <= max ; i++) {
if (map.containsKey(i)) {
for (Integer cur : map.get(i)) {
q.add(cur);
}
}
while (!q.isEmpty() && q.peek() < i) {
q.poll();
}
if (!q.isEmpty()) {
ans++;
q.poll();
}
}
return ans;
}
}
Go代码
package main
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param meetings int整型二维数组
* @return int整型
*/
func attendmeetings(meetings [][]int) int {
//贪心+优先级队列
//自己实现的升序堆,按meetings里的结束时间排序
h := Heap{make([]int, 10), 0}
lastday := -1 //最后会议结束时间
//key: 会议开始是第key天，开始时间的相同的会议的结束时间放同个一list中
daymap := map[int][]int{}
for _, e := range meetings {
start := e[0]
end := e[1]
_, ok := daymap[start]
if !ok {
daymap[start] = []int{}
}
daymap[start] = append(daymap[start], end)
if lastday < end {
lastday = end
}
}
ans := 0
// 整体思路就是从1开始到最晚结束时间依次遍历一遍，然后挑选此时间要进行的会议；
// 而队列的作用就是存储未进行的会议；挑选的判断条件就是挑选的时间不能小于此时的时间，
// 因为队列中存储的是每个会议最晚进行时间，即，结束时间
for i := 1; i <= lastday; i++ {
_, ok := daymap[i]
if ok {
list := daymap[i]
for _, v := range list {
h.add(v)
}
}
for h.Size > 0 && h.peek() < i {
h.remove()
}
if h.Size > 0 {
ans++
h.remove()
}
}
return ans
}
type Heap struct {
Arr []int
Size int
}
func (h *Heap) ensure(length int) { //堆的扩容
old := len(h.Arr)
if old >= length {
return
}
newSize := old + old>>1
newArr := make([]int, newSize)
for i := 0; i < old; i++ {
newArr[i] = h.Arr[i]
}
h.Arr = newArr
}
func (h *Heap) add(x int) { //往堆中添加元素
idx := h.Size
h.ensure(idx + 1)
h.Arr[idx] = x
h.shiftup(idx)
h.Size++
}
func (h *Heap) shiftup(idx int) { //堆的上滤
base := h.Arr[idx]
for idx > 0 {
pid := (idx - 1) >> 1
parent := h.Arr[pid]
if base >= parent {
break
}
h.Arr[idx] = parent
idx = pid
}
h.Arr[idx] = base
}
func (h *Heap) peek() int {
return h.Arr[0]
}
func (h *Heap) remove() int {
ans := h.Arr[0]
idx := h.Size
h.Arr[0] = h.Arr[idx-1]
h.shiftdown(0)
h.Size--
return ans
}
func (h *Heap) shiftdown(idx int) { //下窜，其实可以不传idx,默认是0，从0下标下窜
base := h.Arr[idx]
half := h.Size >> 1
for idx < half {
cidx := idx<<1 + 1
right := cidx + 1
child := h.Arr[cidx]
if right < h.Size && h.Arr[right] < child {
cidx = right
child = h.Arr[right]
}
if base < child {
break
}
h.Arr[idx] = child
idx = cidx
}
h.Arr[idx] = base
}
PHP代码
<?php
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param meetings int整型二维数组
* @return int整型
*/
function attendmeetings( $meetings )
{
//贪心+优先级队列
$ans = 0;
$max = -1; //会议日期最大的那个日期，从每场会议的结束日期里获取
$h = new Heap();
//key: 会议的开始日期start，value:存结束时间的集合list，相同的start的集合
$map = [];
foreach ($meetings as $e){
$start = $e[0];
$end = $e[1];
if(!isset($map[$start])){
$map[$start] =[];
}
$map[$start][count($map[$start])] = $end;
if($max < $end){
$max = $end;
}
}
// 整体思路就是从1开始到最晚结束时间依次遍历一遍，然后挑选此时间要进行的会议；
// 而队列的作用就是存储未进行的会议；挑选的判断条件就是挑选的时间不能小于此时的时间，
// 因为队列中存储的是每个会议最晚进行时间，即，结束时间
for($i=1;$i<=$max;$i++){
if(isset($map[$i])){
$arr = $map[$i];
foreach ($arr as $d){
$h->add($d);
}
}
while ($h->size >0 && $h->peek() <$i){
$h->remove();
}
if ($h->size >0){
$ans++;
$h->remove();
}
}
return $ans;
}
class Heap{ //自己的实现的升序堆
public $arr;
public $size;
public function __construct()
{
//初始化堆
for($i=0;$i<10;$i++){
$this->arr[$i] =0;
}
$this->size =0;
}
public function ensure($cap){ //扩容代码
$old = count($this->arr);
if($old >=$cap) return;
$newsize = $old+$old >>1;
$newarr = [];
for($i=0;$i<$newsize;$i++){
$newarr[$i] =0;
if($i<$old){
$newarr[$i] = $this->arr[$i];
}
}
$this->arr =$newarr;
}
public function add($x){
$idx = $this->size;
$this->ensure($idx+1);
$this->arr[$idx] =$x;
$this->shiftup($idx);
$this->size++;
}
public function shiftup($idx){ //上滤
$base = $this->arr[$idx];
while ($idx >0){
$pid = ($idx-1) >> 1; //父id
$parent = $this->arr[$pid];
if($base >$parent) break;
$this->arr[$idx] = $parent;
$idx = $pid;
}
$this->arr[$idx] = $base;
}
public function peek(){
return $this->arr[0];
}
public function remove(){
$ans =$this->arr[0];
$curlen = $this->size;
$this->arr[0] = $this->arr[$curlen-1];
$this->size--;
$this->shiftdown(0);
return $ans;
}
//下窜，可以不用传idx参数，一般是从0开始下窜，idx=0
public function shiftdown($idx){
$base = $this->arr[$idx];
$half = $this->size >> 1;
while ($idx<$half) {
$cidx = ($idx<<1) +1;
$right = $cidx+1;
$child = $this->arr[$cidx];
if($right < $this->size && $child > $this->arr[$right]){
$cidx = $right;
$child = $this->arr[$right];
}
if($child > $base) break;
$this->arr[$idx] =$child;
$idx= $cidx;
}
$this->arr[$idx] = $base;
}
}
