LeetCode 502. IPO

Categories:

题目描述
思路分析
1. 解法一：双堆贪心（推荐）
相似题目

题目描述

✅ 502. IPO

思路分析

解法一：双堆贪心（推荐）

核心思路：

将项目按资本要求升序排序，用指针逐步加入可启动项目。

用大顶堆维护可选项目的利润，每次选择利润最大的项目。

执行最多 k 轮，若没有可选项目则提前结束。

复杂度分析：

时间复杂度：O(n log n)，其中 n 为项目数量。

空间复杂度：O(n)，堆与排序数组占用。

import java.util.*;

class Solution {
    public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
        int n = profits.length;
        int[][] projects = new int[n][2];
        for (int i = 0; i < n; i++) {
            projects[i][0] = capital[i];
            projects[i][1] = profits[i];
        }
        Arrays.sort(projects, Comparator.comparingInt(a -> a[0]));

        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        int idx = 0;
        long cur = w;

        for (int i = 0; i < k; i++) {
            while (idx < n && projects[idx][0] <= cur) {
                maxHeap.offer(projects[idx][1]);
                idx++;
            }
            if (maxHeap.isEmpty()) {
                break;
            }
            cur += maxHeap.poll();
        }

        return (int) cur;
    }
}

import (
    "container/heap"
    "sort"
)

type MaxHeap []int

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

func findMaximizedCapital(k int, w int, profits []int, capital []int) int {
    n := len(profits)
    projects := make([][2]int, n)
    for i := 0; i < n; i++ {
        projects[i] = [2]int{capital[i], profits[i]}
    }
    sort.Slice(projects, func(i, j int) bool {
        return projects[i][0] < projects[j][0]
    })

    h := &MaxHeap{}
    heap.Init(h)
    idx := 0
    cur := w

    for i := 0; i < k; i++ {
        for idx < n && projects[idx][0] <= cur {
            heap.Push(h, projects[idx][1])
            idx++
        }
        if h.Len() == 0 {
            break
        }
        cur += heap.Pop(h).(int)
    }

    return cur
}

相似题目

题目	难度	考察点
253. 会议室 II	中等	堆
630. 课程表 III	困难	贪心 + 堆
1353. 最多可以参加的会议数目	中等	堆
857. 雇佣 K 名工人的最低成本	困难	堆
1383. 最大的团队表现值	中等	排序 + 堆

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2023/19708323