列表

详情


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

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

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

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

 

示例 1:

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

示例 2:

输入:events= [[1,2],[2,3],[3,4],[1,2]]
输出:4

 

提示:​​​​​​

原站题解

去查看

上次编辑到这里,代码来自缓存 点击恢复默认模板
class Solution { public: int maxEvents(vector<vector<int>>& events) { } };

php 解法, 执行用时: 988 ms, 内存消耗: 142.5 MB, 提交时间: 2023-08-22 10:22:56

class Solution {

    /**
     * @param Integer[][] $events
     * @return Integer
     */
    function maxEvents($events) {
        $stack1 = new SplMinHeap();
        $stack2 = new SplMinHeap();
        $cur = PHP_INT_MAX;
        foreach($events as $k=>$e){
            $stack1->insert([$e[0],$e[1],$k]);
            $stack2->insert([$e[1],$e[0],$k]);
            $cur = min($cur,$e[0]);
        }
        $res = 0;
        $cache = [];
        while($stack2->isEmpty() === false && $stack1->isEmpty() === false){
            $top1 = $stack1->top();
            $top2 = $stack2->top();
            //var_dump(json_encode($top1).";".json_encode($top2).";cur:$cur;res:$res;cache:".json_encode($cache));
            if($top2[1] <= $cur && $top2[0] >= $cur){
                //var_dump("if");
                $stack2->extract();
                if(isset($cache[$top2[2]]))continue;
                $cache[$top2[2]] = 1;
                $cur += 1;
                ++$res;
            }elseif($top1[0] <= $cur && $top1[1] >= $cur){
                //var_dump("elseif");
                $stack1->extract();
                if(isset($cache[$top1[2]]))continue;
                $cache[$top1[2]] = 1;
                $cur += 1;
                ++$res;
            }
            while($stack1->isEmpty() === false && $stack1->top()[1] < $cur)$stack1->extract();
            while($stack2->isEmpty() === false && $stack2->top()[0] < $cur)$stack2->extract();
            if($stack1->isEmpty() || $stack2->isEmpty())break;
            if($cur < $stack1->top()[0]) $cur = $stack1->top()[0];
        }
        return $res;
    }
}

golang 解法, 执行用时: 300 ms, 内存消耗: 20 MB, 提交时间: 2023-08-22 10:18:38

// 在当前可以参加的会议中,使用堆去找最早到期的会议参加。
func maxEvents(events [][]int) int {
    sort.SliceStable(events, func(i,j int)bool{
        return events[i][0] < events[j][0]
    })
    h := hp{}
    count := 0

    for time := 0; time < 1e5 + 1; time ++{
        for len(events) > 0{
            if time >= events[0][0]{
                h.push(events[0][1])
                events = events[1:]
                continue
            }
            break
        }
        for h.Len() > 0 && time > h.top(){
            h.pop()
        }
        if h.Len() > 0 && time <= h.pop(){
            count ++
        }
    }
    return count
}

type hp struct{ sort.IntSlice }
func (h *hp) Push(v interface{}) { h.IntSlice = append(h.IntSlice, v.(int)) }
func (h *hp) Pop() interface{}   { a := h.IntSlice; v := a[len(a)-1]; h.IntSlice = a[:len(a)-1]; return v }
func (h hp) Less(i, j int) bool { return h.IntSlice[i] < h.IntSlice[j] }
func (h *hp) push(v int)         { heap.Push(h, v) }
func (h *hp) pop() int           { return heap.Pop(h).(int) }
func (h hp) empty() bool         { return len(h.IntSlice) == 0 }
func (h hp) top() int            { return h.IntSlice[0] }

python3 解法, 执行用时: 420 ms, 内存消耗: 54.1 MB, 提交时间: 2023-08-22 10:17:28

class Solution:
    def maxEvents(self, events: List[List[int]]) -> int:
        ans, T = 0, 0 # 记录参加的会议数目,最大天数
        # dic_evt[i]是列表,包含在第i天开始的会所有议的结束时间; T是总时间长度
        dic_evt = defaultdict(list)
        for evt in events:
            dic_evt[evt[0]].append(evt[1])
            T = max(T, evt[1])
        # 对时间1~T遍历 每个时刻t,que_able保存当前可参加的会议的结束时间
        que_able = []
        for t in range(1, T+1):
            for end in dic_evt[t]: heapq.heappush(que_able, end)
            # pop结束时间小于t的会议 参加结束时间大于t的会议中结束时间最早的
            while que_able and que_able[0] < t: heapq.heappop(que_able)
            # 此时que_able中都是结束时间大于t的会议所对应的结束时间
            if que_able:
                ans += 1
                heapq.heappop(que_able)
        return ans

cpp 解法, 执行用时: 456 ms, 内存消耗: 188.7 MB, 提交时间: 2023-08-22 10:14:46

/**
 * 扫描算法+贪心
 * 
 */
const int MAX = 1e5 + 1;

class Solution {
public:
    int maxEvents(vector<vector<int>>& events) {
        vector<vector<int>> left(MAX);
        for (int i = 0; i < events.size(); ++i)
            left[events[i][0]].emplace_back(i);
        
        int ans = 0;
        priority_queue<int, vector<int>, greater<>> pq;
        for (int i = 1; i < MAX; ++i) {
            for (int j : left[i])
                pq.push(events[j][1]);
            while (!pq.empty() && pq.top() < i)
                pq.pop();
            if (!pq.empty()) {
                pq.pop();
                ans++;
            }
        }
        return ans;
    }
};

上一题