前言

例题

1. 最小区间

描述

思路
给定 k个列表，需要找到最小区间，使得每个列表都至少有一个数在该区间中。该问题可以转化为，从 k 个列表中各取一个数，使得这 k 个数中的最大值与最小值的差最小。

由于 k 个列表都是升序排列的，因此对每个列表维护一个指针，通过指针得到列表中的元素，指针右移之后指向的元素一定大于或等于之前的元素。

使用最小堆维护 k 个指针指向的元素中的最小值，同时维护堆中元素的最大值。初始时，k 个指针都指向下标 0，最大元素即为所有列表的下标 0 位置的元素中的最大值。每次从堆中取出最小值，根据最大值和最小值计算当前区间，如果当前区间小于最小区间则用当前区间更新最小区间，然后将对应列表的指针右移，将新元素加入堆中，并更新堆中元素的最大值。

如果一个列表的指针超出该列表的下标范围，则说明该列表中的所有元素都被遍历过，堆中不会再有该列表中的元素，因此退出循环。

代码
Python代码：

class Solution:
    def smallestRange(self, nums: List[List[int]]) -> List[int]:
        import heapq
        left_range, right_range = -10**9, 10**9
        # 提前求最大值
        max_value = max(vec[0] for vec in nums)
        # 堆，保留行数和索引
        priority_queue = [(vec[0], i, 0) for i, vec in enumerate(nums)]
        heapq.heapify(priority_queue)
        while True:
            min_value, row, idx = heapq.heappop(priority_queue)
            if right_range - left_range > max_value - min_value:
                left_range, right_range = min_value, max_value
            # 这里是退出的条件，当idx遍历完
            if idx == len(nums[row]) - 1:
                break
            # 更新最大值
            max_value = max(max_value, nums[row][idx + 1])
            # 入堆，同样是元组形式
            heapq.heappush(priority_queue,(nums[row][idx + 1], row, idx+1))
        return [left_range, right_range]

Java代码：

class Solution {
    public int[] smallestRange(List<List<Integer>> nums) {
        int rangeLeft = 0, rangeRight = Integer.MAX_VALUE;
        int minRange = rangeRight - rangeLeft;
        int max = Integer.MIN_VALUE;
        int size = nums.size();
        int[] next = new int[size];
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new Comparator<Integer>(){
            public int compare(Integer index1, Integer index2) {
                return nums.get(index1).get(next[index1]) - nums.get(index2).get(next[index2]);
            }
        });
        for (int i = 0; i < size; i++) {
            priorityQueue.offer(i);
            max = Math.max(max, nums.get(i).get(0));
        }
        while (true) {
            int minIndex = priorityQueue.poll();
            int curRange = max - nums.get(minIndex).get(next[minIndex]);
            if (curRange < minRange) {
                minRange = curRange;
                rangeLeft = nums.get(minIndex).get(next[minIndex]);
                rangeRight = max;
            }
            next[minIndex]++;
            if (next[minIndex] == nums.get(minIndex).size()) {
                break;
            }
            priorityQueue.offer(minIndex);
            max = Math.max(max, nums.get(minIndex).get(next[minIndex]));
        }
        return new int[]{rangeLeft, rangeRight};
    }
}

2. 猿辅导-小猿上课

描述
小猿非常热爱学习，所以他在猿辅导上购买了NN节课来提升自己，每节课有一个开始时间SS和结束时间EE（SS和EE均用正整数表示）。买完课程后，粗心的小袁发现这些课程之间有些时间冲突，幸好小猿有一种“一心多用”的超能力，能同时兼顾KK节课上课。当然是KK越大，使用这种能力就越累。请问小猿最少需要一心几用，才能上完所有他买的课程呢？输入描述第一行输入为NN（N≤200000N≤200000），表示购买课程数。接下来NN行，每行输入两个数Si、EiSi、Ei（0输入
41 41 22 33 4
输出
2
思路

区间问题一般都要排序，按起始点或者按终点
按开始时间和结束时间从小到大排序
使用堆维护时间区间，对于排序后两个课程a和b来说，如果a和b无法分开上，则须满足b的开始时间小于a的结束时间
答案为堆中同时存在的课程数量的最大值

代码
Python代码：

import heapq
n = int(input())
start_end_list = [list(map(int, input().split())) for _ in range(n)]
start_end_list.sort(key=lambda x: x[0])
q = []
res = 0
heapq.heapify(q)
for start, end in start_end_list:
    while q and q[0] <= start:
        heapq.heappop(q)
    heapq.heappush(q, end)
    res = max(res, len(q))
print(res)

3.堆排序

代码

import java.util.*;

public class Main {
    public static int size = 0;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        size = n;
        int[] a = new int[n+1];
        for (int i = 1; i <= n; i++) {
            a[i] = in.nextInt();
        }
        for (int i = n / 2; i >= 1; i--) {
            down(a, i);
        }
        while (m > 0) {
            System.out.print(a[1] + " ");
            swap(a, 1, size--);
            down(a, 1);
            m--;
        }

    }
    public static void down(int[] a, int i) {
        int j = i;
        if (2 * i <= size && a[j] > a[2 * i]) {
            j = 2 * i;
        }
        if (2 * i + 1 <= size && a[j] > a[2 * i + 1]) {
            j = 2 * i + 1;
        }
        if (j != i) {
            swap(a, i, j);
            down(a, j);
        }
    }
    public static void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}

4. 最少加油次数

思路

代码

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        int L = in.nextInt();
        int P = in.nextInt();
        int[] A = new int[N+1];
        int[] B = new int[N+1];
        for (int i = 0; i < N; i++) {
            A[i] = in.nextInt();
        }
        for (int i = 0; i < N; i++) {
            B[i] = in.nextInt();
        }

        A[N] = L;
        B[N] = 0;
        N++;
        PriorityQueue<Integer> q = new PriorityQueue<>(((o1, o2) -> o2 - o1));
        int ans = 0, pos = 0, tank = P;
        for (int i = 0; i < N; i++) {
            int d = A[i] - pos;
            while (tank - d < 0) {
                if (q.isEmpty()) {
                    System.out.println(-1);
                    return;
                }
                tank += q.peek();
                q.poll();
                ans++;
            }
            tank -= d;
            pos = A[i];
            q.offer(B[i]);
        }
        System.out.println(ans);
    }
}

5. Fence Repair

思路

优先级队列，贪心算法

代码

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        int[] L = new int[N];
        for (int i = 0; i < N; i++) {
            L[i] = in.nextInt();
        }
        int ans = 0;
        PriorityQueue<Integer> q = new PriorityQueue<>();
        for (int i = 0; i < N; i++) {
            q.offer(L[i]);
        }
        while (q.size() > 1) {
            int l1, l2;
            l1 = q.peek();
            q.poll();
            l2 = q.peek();
            q.poll();
            ans += l1 + l2;
            q.offer(l1 + l2);
        }
        System.out.println(ans);
    }
}