โปรแกรมหาความต่างน้อยสุดระหว่างค่าสูงสุดและต่ำสุดจากการเลือกสมาชิกแต่ละลิสต์ใน C++

สมมติว่าเรามีลิสต์ของลิสต์หลายๆ ลิสต์ ต้องการเลือกสมาชิกหนึ่งตัวจากแต่ละลิสต์ แล้วหาความต่างระหว่างค่าสูงสุดและต่ำสุดของตัวที่เลือก ให้หาความต่างน้อยสุดที่เป็นไปได้

ตัวอย่าง: lists = [[30, 50, 90], [85], [35, 70]] ผลลัพธ์คือ 20 เลือก 90, 85, 70 ความต่าง = 90 - 70 = 20

ขั้นตอนการแก้ปัญหา

1. maxVal := -infinity, ret := infinity
2. สร้าง Priority Queue (Min-Heap) pq
3. n := จำนวนลิสต์
4. สำหรับแต่ละลิสต์ i:
   • เรียงลำดับลิสต์ i
   • ใส่ {lists[i][0], i, 0} เข้า pq (ค่า, ลิสต์ที่, ดัชนี)
   • อัปเดต maxVal = max(maxVal, lists[i][0])
5. เมื่อขนาด pq เท่ากับ n (ยังมีสมาชิกจากทุกลิสต์):
   • temp := pop ตัวเล็กที่สุดจาก pq
   • ret = min(ret, maxVal - temp[0])
   • เพิ่มดัชนีของ temp (temp[2]++)
   • ถ้ายังมีสมาชิกในลิสต์เดิม:
     • ค่าใหม่ = lists[temp[1]][temp[2]]
     • maxVal = max(maxVal, ค่าใหม่)
     • temp[0] = ค่าใหม่
     • push temp กลับเข้า pq
6. คืนค่า ret

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

struct Cmp {
    bool operator()(vector<int>& a, vector<int>& b) {
        return !(a[0] < b[0]);
    }
};

class Solution {
public:
    int solve(vector<vector<int>>& lists) {
        int maxVal = INT_MIN;
        int ret = INT_MAX;
        priority_queue<vector<int>, vector<vector<int>>, Cmp> pq;
        int n = lists.size();
        
        for (int i = 0; i < n; i++) {
            sort(lists[i].begin(), lists[i].end());
            pq.push({lists[i][0], i, 0});
            maxVal = max(lists[i][0], maxVal);
        }
        
        while (pq.size() == n) {
            vector<int> temp = pq.top();
            pq.pop();
            ret = min(ret, maxVal - temp[0]);
            temp.back()++;
            if (temp.back() < lists[temp[1]].size()) {
                maxVal = max(maxVal, lists[temp[1]][temp.back()]);
                temp[0] = lists[temp[1]][temp.back()];
                pq.push(temp);
            }
        }
        return ret;
    }
};

int solve(vector<vector<int>>& lists) {
    return (new Solution())->solve(lists);
}

int main() {
    vector<vector<int>> v = {{30, 50, 90}, {85}, {35, 70}};
    cout << solve(v);
    return 0;
}

อินพุต

{{30, 50, 90}, {85}, {35, 70}}

เอาต์พุต

20