LeetCode 1353. 最多可以参加的会议数目

Categories:

题目描述
思路分析
1. 解法一：排序 + 小根堆（推荐）
相似题目

题目描述

✅ 1353. 最多可以参加的会议数目

思路分析

解法一：排序 + 小根堆（推荐）

核心思路：

按会议开始时间排序。

用小根堆维护当前可参加会议的结束时间。

逐日推进：

将当天开始的会议加入堆。

移除已过期会议（结束时间 < 当前天）。

若堆非空，参加结束最早的会议。

复杂度分析：

时间复杂度：O(n log n)，其中 n 表示会议数量。

空间复杂度：O(n)。

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

class Solution {
    public int maxEvents(int[][] events) {
        Arrays.sort(events, (a, b) -> a[0] - b[0]);

        int maxDay = 0;
        for (int[] e : events) {
            maxDay = Math.max(maxDay, e[1]);
        }

        PriorityQueue<Integer> pq = new PriorityQueue<>();
        int i = 0;
        int ans = 0;

        for (int day = 1; day <= maxDay; day++) {
            while (i < events.length && events[i][0] == day) {
                pq.offer(events[i][1]);
                i++;
            }

            while (!pq.isEmpty() && pq.peek() < day) {
                pq.poll();
            }

            if (!pq.isEmpty()) {
                pq.poll();
                ans++;
            }
        }

        return ans;
    }
}

import (
	"container/heap"
	"sort"
)


type IntHeap []int

func (h IntHeap) Len() int           { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *IntHeap) Push(x interface{}) {
	*h = append(*h, x.(int))
}
func (h *IntHeap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[:n-1]
	return x
}

func maxEvents(events [][]int) int {
	sort.Slice(events, func(i, j int) bool {
		return events[i][0] < events[j][0]
	})

	maxDay := 0
	for _, e := range events {
		if e[1] > maxDay {
			maxDay = e[1]
		}
	}

	pq := &IntHeap{}
	heap.Init(pq)

	ans := 0
	i := 0
	for day := 1; day <= maxDay; day++ {
		for i < len(events) && events[i][0] == day {
			heap.Push(pq, events[i][1])
			i++
		}

		for pq.Len() > 0 && (*pq)[0] < day {
			heap.Pop(pq)
		}

		if pq.Len() > 0 {
			heap.Pop(pq)
			ans++
		}
	}

	return ans
}

相似题目

题目	难度	考察点
1353. 最多可以参加的会议数目	中等	贪心、堆
253. 会议室 II	中等	堆
1094. 拼车	中等	差分
435. 无重叠区间	中等	贪心
452. 用最少数量的箭引爆气球	中等	贪心
502. IPO	困难	堆、贪心

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2021/90498129