當有多個來源（ex: k 個排序好的序列、或 k 條任務流水線），需要按時間/優先級合併處理時可以用priority queue來解。

我們直接練習個幾題

leetcode 373. Find K Pairs with Smallest Sums

題目：給兩個已經排好順序的數字陣列和常數k，從兩個陣列中各取一個值，回傳前k個總和最小的組合
輸入：nums1 = [1,7,11], nums2 = [2,4,6], k = 3
輸出：[[1,2],[1,4],[1,6]]
限制：

• <= nums1.length, nums2.length <= 10^5
• -10^9 <= nums1[i], nums2[i] <= 10^9
• nums1 and nums2 both are sorted in non-decreasing order.
• 1 <= k <= 10^4
• k <= nums1.length * nums2.length

解法：一開始想用暴力解列出全部的值O(m*n)，在把總和排序O(m**n log m**n)，當陣列給多時會ETL，因為輸入陣列已經排好順序，所以能肯定的是最小和的一定是個拿第一個值，接著再從第一個值去推，nums1維持原狀nums2往下拿，或是nums1往下拿nums2維持原狀，以此類推直到拿到前k個值最小的。

1. 從(0,0)開始找最小的和，我們會往下推比較(0,1)、(1,0)
2. 如果(1,0)的和最小，我們拿走(1,0)剩下(0,1)、(1,1)、(2,0)備選
3. 往下一步(2,0)的和最小，(0,1)、(1,1)、(2,1)、(3,0)備選
4. 以此類推每次都從上次落選的組合加上(num1+1,num2)和(num1,num2+1)中找出最小的和，像不像min heap pop()得到的值。

拿到重複的怎辦

1. 當我們選到(2,0)下一顧備選的會是(0,1)、(1,1)、(2,1)、(3,0)
2. 下一個最小值(0,1)，備選的會是(1,1)、(2,1)、(3,0)、(1,1)、(0,2)，(1,1)這裡(1,1)重複了
3. (1,1)只能拿一個，所以要記錄目前有沒有拿過，可以用hashset來記錄

use std::collections::{BinaryHeap,HashSet};
use std::cmp::Reverse;

impl Solution {
    pub fn k_smallest_pairs(nums1: Vec<i32>, nums2: Vec<i32>, k: i32) -> Vec<Vec<i32>> {
        let mut heap = BinaryHeap::new();
        let mut hash_set = HashSet::new();

        let mut ans = Vec::new();
        heap.push((Reverse(nums1[0]+nums2[0]),0,0));

        while(!heap.is_empty()){
            let Some((_,n1,n2)) = heap.pop() else {todo!()};
            ans.push(vec!(nums1[n1],nums2[n2]));
            
            if(ans.len()>=k as usize) {
                break
            }
            if(n1 as usize ==nums1.len()-1 && n2 as usize ==nums2.len()-1){
                continue
            }

            if(n1 as usize >=nums1.len()-1){
                if(!hash_set.contains(&(n1,n2+1))){
                    heap.push((Reverse(nums1[n1 as usize]+nums2[(n2+1) as usize]),n1,n2+1));
                    hash_set.insert((n1,n2+1));
                }
            } else if(n2 as usize >=nums2.len()-1){
                if(!hash_set.contains(&(n1+1,n2))){
                    heap.push((Reverse(nums1[(n1+1) as usize]+nums2[n2 as usize]),n1+1,n2));
                    hash_set.insert((n1+1,n2));
                }
            } else {
                if(!hash_set.contains(&(n1+1,n2))){
                    heap.push((Reverse(nums1[(n1+1) as usize]+nums2[n2 as usize]),n1+1,n2));
                    hash_set.insert((n1+1,n2));
                }
                
                if(!hash_set.contains(&(n1,n2+1))){
                    heap.push((Reverse(nums1[n1 as usize]+nums2[(n2+1) as usize]),n1,n2+1));
                    hash_set.insert((n1,n2+1));
                }
            }
        }

        ans
    }
}

解法優化：

1. 一開始[1,7,11]、[2,4,6] 先選擇(0,0) 將(0,1)、(1,0)放入min heap 比較最小和
2. 再來選(0,1) 將(0,2)、(1,1) push到min heap，(1,0)、(0,2)、(1,1)，因為有排序過的陣列(1,0)<(1,1)
3. 以此類推我們只要知道(n1,n2+1) 跟(n1+1,0)、(n1+1,1)……(n1+1,n2)其中還沒用過最小值比較就好，沒有重複可以省略查詢重複的時間

use std::collections::BinaryHeap;
use std::cmp::Reverse;
impl Solution {
    pub fn k_smallest_pairs(nums1: Vec<i32>, nums2: Vec<i32>, k: i32) -> Vec<Vec<i32>> {
        let chose = (nums1.len() as i32).min(k); //juse take k pairs
        let mut heap = BinaryHeap::new();
        let mut ans = Vec::new();
        for i in 0..chose as usize {
            heap.push((Reverse(nums1[i]+nums2[0]),i as usize,0 as usize))
        }

        while(ans.len()< k as usize){
            let Some((_,n1,n2)) = heap.pop() else {todo!()};
            ans.push(vec!(nums1[n1],nums2[n2]));
            if n2+1<nums2.len() {
                heap.push((Reverse(nums1[n1]+nums2[n2+1]),n1,n2+1));
            }
        }
        ans
    }
}

時間複雜度:O(klogk)

leetcode 621. Task Scheduler

題目：給一連串代號A、Ｂ、Ｃ…Z的任務，並設定一個區間n，在區間n內不能執行重複任務，最短能在幾個區間內執行完成
輸入：tasks = ["A","A","A","B","B","B"], n = 2
輸出：8 因為A→B→idle→A→B→idle→A→B
限制：

• 1 <= tasks.length <= 10^4
• tasks[i] is an uppercase English letter.
• 0 <= n <= 100

priority queue 解法：

1. 要如何排任務順序，出現越多的排越前面，ex [“A“,”A”,”B”,”C”] n=2，A→B→C→A只要4 B→A→C→idle→A要5
2. 多的排越前面符合priority queue特性，我們用max heap來排順序
3. 因為間隔n所以每一回合挑選前n+1個出現最多的任務，回合後將出現次數-1放回max heap，持續到任務全部做完。

use std::collections::{BinaryHeap,HashMap};
use std::cmp::Reverse;

impl Solution {
    pub fn least_interval(tasks: Vec<char>, n: i32) -> i32 {
        //get freq

        let mut cnt = [0;26];
        for &c in &tasks {
            cnt[(c as u8 -b'A') as usize]+=1;
        }
        let mut heap = BinaryHeap::new();
        for (idx,freq) in cnt.into_iter().enumerate() {
            if(freq>0){
                heap.push((freq,Reverse(idx)));
            }
        }
        let mut ans =0;
        

        while(heap.len()>0){
            let mut count = n +1 ;
            let mut temp = Vec::new();
            while(count>0){
                if let Some((freq,Reverse(c))) = heap.pop() {
                    ans+=1;
                    if(freq-1>0){
                        temp.push((freq-1,Reverse(c)));
                    }
                    count-=1;
                } else {
                    if(temp.len()==0){
                        break
                    }
                    ans+=1;
                    count-=1;
                }
            }

            for element in temp.into_iter() {
                heap.push(element);
            }
            
        }
        ans
    }
}

時間複雜度:O(mlogk)

1. 統計出現頻率 O(m)，n被當參數用m來代替tasks.len()
2. 建heap O(klogk) k=26
3. 排任務：O(mlogk)，回圈最多執行m次，k為每次push、pop 時間

Day18 總結

1.Priority Queue 多來源、多任務題型練習