Tìm phần tử nhỏ thứ k trong n khoảng cho trước trong C++

Cho n khoảng [L, R] và số k. Nhiệm vụ: tìm phần tử nhỏ thứ k trong n khoảng.

Gộp các khoảng thành mảng đã sắp xếp, lấy phần tử thứ k.

Ví dụ:

Đầu vào: ranges = {{2, 5}, {7, 9}, {12, 15}}, k = 9

Đầu ra: 13

Giải thích:

Mảng gộp: {2, 3, 4, 5, 7, 8, 9, 12, 13, 14, 15}. Phần tử nhỏ thứ 9 là 13.

Phương pháp giải

Tạo mảng từ các khoảng (đã sắp xếp do khoảng liên tục). Lấy phần tử tại chỉ mục k-1 (0-based).

Chương trình minh họa

Ví dụ

#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];
    int size = 0;
    for (int i = 0; i < n; i++)
        for (int j = arr[i][0]; j <= arr[i][1]; j++) {
            rangeArr[size] = j;
            size++;
        }
    if (k < size)
        cout << k << "th smallest element of the ranged array is " << rangeArr[k] << endl;
    else
        cout << "invalid Index";
    return 0;
}

Kết quả

9th smallest element of the ranged array is 13