หา K-th Element ใน Series จาก N ช่วง (Ranges) ใน C++

ในปัญหานี้ เราได้รับ N ช่วง [L, R] และค่า K งานคือหา K-th element ใน series ที่รวมตัวเลขทุกช่วงเข้าด้วยกัน (เรียงเลขไม่ซ้ำ)

ตัวอย่าง

Input: ranges = {{1, 3}, {5, 7}}, k = 4 Output: 5

Series: {1, 2, 3, 5, 6, 7} → 4th = 5

วิธีที่ 1: สร้าง Array โดยตรง (ใช้หน่วยความจำมาก)

รวมทุกตัวเลขในช่วงเข้า array แล้วหา index k-1

วิธีที่ 2: Binary Search + Prefix Count (แนะนำ) O(N log MaxRange)

1. สร้าง prefix count array: count[i] = จำนวนตัวเลขสะสมถึงช่วง i
2. Binary search หาช่วงที่มี K-th element
3. Binary search อีกครั้งในช่วงนั้นเพื่อหาค่าที่แน่นอน

ตัวอย่างโค้ด (วิธีที่ 2)

#include <iostream>
using namespace std;

int findKthElement(int n, int k, int range[][2]) {
    vector count(n + 1, 0);
    for (int i = 0; i < n; i++)
        count[i + 1] = count[i] + (range[i][1] - range[i][0] + 1);
    
    // Binary search หาช่วง
    int idx = -1, lo = 1, hi = n;
    while (lo <= hi) {
        int mid = (lo + hi) / 2;
        if (count[mid] >= k) { idx = mid; hi = mid - 1; }
        else lo = mid + 1;
    }
    
    // Binary search ในช่วงที่ idx
    int L = range[idx - 1][0], R = range[idx - 1][1];
    int target = k - count[idx - 1];
    lo = L; hi = R;
    while (lo <= hi) {
        int mid = (lo + hi) / 2;
        if (mid - L + 1 == target) return mid;
        else if (mid - L + 1 > target) hi = mid - 1;
        else lo = mid + 1;
    }
    return -1;
}

int main() {
    int range[][2] = {{1, 3}, {5, 8}};
    cout << findKthElement(2, 4, range); // 5
    return 0;
}

ผลลัพธ์

4-th element of the series generated by ranges is 5