หาเลขที่ k-th น้อยที่สุดใน n ช่วง (Ranges) ใน C++

โจทย์

ได้รับ n ช่วงตัวเลข และจำนวน k ทางเราต้อง หาเลขที่ k-th น้อยที่สุดจากชุดตัวเลขที่รวมจากทุกช่วง

ตัวอย่าง

Input: ranges = {{2,5}, {7,9}, {12,15}}, k = 9

Output: 13

อธิบาย: ชุดตัวเลขรวม: {2,3,4,5,7,8,9,12,13,14,15} -> ตัวที่ 9 คือ 13

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

วิธีแบบง่าย: สร้างอาร์เรย์รวมจากทุกช่วง (อยู่แล้วเรียง) แล้วหาตัวที่ k-1

หมายเหตุ: วิธีนี้ใช้หน่วยความจำมากถ้าช่วงกว้าง ควรใช้ Binary Search บนคำตอบพร้อมฟังก์ชันนับจำนวน ≤ x

โปรแกรมตัวอย่าง (วิธีแบบง่าย)

#include <iostream>
using namespace std;

int main() {
    int arr[][2] = {{2, 5}, {7, 9}, {12, 15}};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 9;
    int rangeArr[1000], size = 0;
    for (int i = 0; i < n; i++)
        for (int j = arr[i][0]; j <= arr[i][1]; j++)
            rangeArr[size++] = j;
    if (k < size)
        cout << k << "th smallest element of the ranged array is " << rangeArr[k-1] << endl;
    else
        cout << "invalid Index";
    return 0;
}

ผลลัพธ์

9th smallest element of the ranged array is 13