หา K รายการที่มีค่าต่ำสุดใน C++

โจทย์

ได้รับรายการที่มีคู่ (Item, Value) และจำนวน k ทางเราต้อง หา K รายการที่มีค่าต่ำสุด

ตัวอย่าง

Input: items = {{item1,200}, {item2,100}, {item3,500}, {item4,400}}, k = 2

Output: item2, item1 (เรียงตามค่า)

แนวทางแก้ปัญหา

เรียงรายการตามค่า (Value) จากน้อยไปมาก แล้วเลือก k ตัวแรก

โปรแกรมตัวอย่าง

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

bool compVal(pair<string, int> A, pair<string, int> B) {
    if (A.second == B.second) return A.first < B.first;
    return A.second < B.second;
}

int main() {
    int k = 2, n = 3;
    vector<pair<string, int>> items;
    items.push_back({"item1", 350});
    items.push_back({"item2", 150});
    items.push_back({"item3", 500});
    items.push_back({"item4", 100});
    sort(items.begin(), items.end(), compVal);
    cout << k << " items with least value are \n";
    for (int i = 0; i < min(n, k); ++i)
        cout << "Item : " << items[i].first << ", value : " << items[i].second << endl;
    return 0;
}

ผลลัพธ์

2 items with least value are Item : item4, value : 100 Item : item2, value : 150