Bài toán yêu cầu chúng ta, với một tập hợp gồm n khoảng giá trị (interval) và m điểm truy vấn (query point), hãy tìm độ dài của khoảng giá trị ngắn nhất chứa mỗi điểm truy vấn. Nếu một điểm truy vấn không nằm trong bất kỳ khoảng giá trị nào, kết quả trả về sẽ là -1. Đây là một vấn đề phổ biến trong lập trình thi đấu, thường được giải quyết bằng các cấu trúc dữ liệu hiệu quả.
Tiếp cận 1: Sử dụng cấu trúc Map phức tạp (Độ phức tạp cao, dễ sai sót)
Một số giải pháp ban đầu có thể nghĩ đến việc sử dụng các cấu trúc dữ liệu như std::map để quản lý các khoảng giá trị đang hoạt động và nhanh chóng tìm ra khoảng ngắn nhất. Ý tưởng là duy trì một tập hợp các khoảng hợp lệ, được sắp xếp theo độ dài, và một cơ chế để loại bỏ nhanh các khoảng không còn hợp lệ khi điểm truy vấn di chuyển.
Tuy nhiên, việc triển khai giải pháp này bằng cách sử dụng hai map để theo dõi đồng thời độ dài và điểm kết thúc của các khoảng có thể trở nên cực kỳ phức tạp. Các thao tác chèn, cập nhật và xóa trên hai map cần được đồng bộ hóa cẩn thận, dễ dẫn đến lỗi logic và khó gỡ rối. Vì độ phức tạp cao và tiềm ẩn nhiều sai sót, cách tiếp cận này thường không được khuyến khích trong thực tế.
Tiếp cận 2: Sử dụng Hàng đợi ưu tiên (Priority Queue) (Được khuyến nghị)
Đây là một trong những phương pháp hiệu quả và dễ hiểu nhất để giải quyết bài toán này. Ý tưởng chính là sắp xếp cả các khoảng giá trị và các điểm truy vấn, sau đó sử dụng một hàng đợi ưu tiên (min-heap) để quản lý các khoảng hợp lệ.
- Kết hợp các điểm truy vấn với chỉ mục gốc của chúng và sắp xếp chúng theo giá trị tăng dần.
- Sắp xếp các khoảng giá trị theo điểm bắt đầu tăng dần.
- Duyệt qua các điểm truy vấn đã sắp xếp. Với mỗi điểm truy vấn:
- Thêm tất cả các khoảng giá trị mới có điểm bắt đầu nhỏ hơn hoặc bằng điểm truy vấn hiện tại vào hàng đợi ưu tiên. Hàng đợi ưu tiên này sẽ được sắp xếp theo độ dài của khoảng giá trị (ưu tiên ngắn nhất), và mỗi phần tử cũng sẽ lưu trữ điểm kết thúc của khoảng.
- Loại bỏ khỏi hàng đợi ưu tiên tất cả các khoảng mà điểm kết thúc của chúng đã nhỏ hơn điểm truy vấn hiện tại (tức là không còn chứa điểm truy vấn này nữa).
- Sau khi cập nhật hàng đợi, khoảng giá trị ở đầu hàng đợi (nếu không rỗng) sẽ là khoảng ngắn nhất hiện tại chứa điểm truy vấn. Ghi lại độ dài của nó vào vị trí kết quả tương ứng.
#include <vector>
#include <algorithm>
#include <queue> // Cho std::priority_queue
#include <utility> // Cho std::pair
class XuLyKhoangToiUu {
public:
// Hàm tìm độ dài khoảng ngắn nhất chứa mỗi điểm truy vấn
std::vector<int> timDoDaiKhoangNganNhat(std::vector<std::vector<int>>& cacKhoang, std::vector<int>& cacTruyVan) {
// Chuẩn bị danh sách truy vấn kèm chỉ mục gốc để lưu kết quả đúng vị trí
// Mỗi phần tử là một cặp: {giá trị truy vấn, chỉ mục ban đầu}
std::vector<std::pair<int, int>> truyVanVaChiMuc;
for (int i = 0; i < cacTruyVan.size(); ++i) {
truyVanVaChiMuc.push_back({cacTruyVan[i], i});
}
// Sắp xếp các khoảng theo điểm bắt đầu tăng dần
std::sort(cacKhoang.begin(), cacKhoang.end());
// Sắp xếp các truy vấn theo giá trị điểm truy vấn tăng dần
std::sort(truyVanVaChiMuc.begin(), truyVanVaChiMuc.end());
// Vector lưu trữ kết quả, khởi tạo với giá trị -1
std::vector<int> ketQua(cacTruyVan.size(), -1);
// Hàng đợi ưu tiên (min-heap) để lưu các khoảng hợp lệ hiện tại.
// Ưu tiên các khoảng có độ dài nhỏ nhất.
// Mỗi phần tử là một cặp: {độ dài khoảng, điểm kết thúc khoảng}
std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<std::pair<int, int>>> hangDoiUuTien;
int chiMucKhoangHienTai = 0; // Con trỏ để duyệt qua danh sách các khoảng đã sắp xếp
// Duyệt qua từng truy vấn đã được sắp xếp
for (auto& truyVanEntry : truyVanVaChiMuc) {
int diemTruyVan = truyVanEntry.first;
int chiMucGoc = truyVanEntry.second;
// Bước 1: Thêm các khoảng mới vào hàng đợi ưu tiên.
// Các khoảng có điểm bắt đầu nhỏ hơn hoặc bằng điểm truy vấn hiện tại.
while (chiMucKhoangHienTai < cacKhoang.size() && cacKhoang[chiMucKhoangHienTai][0] <= diemTruyVan) {
// Chỉ thêm khoảng nếu nó có thể chứa điểm truy vấn (tức là điểm kết thúc >= điểm truy vấn).
// Mặc dù chúng ta sẽ loại bỏ sau, việc kiểm tra sớm giúp giảm tải cho hàng đợi.
if (cacKhoang[chiMucKhoangHienTai][1] >= diemTruyVan) {
int doDai = cacKhoang[chiMucKhoangHienTai][1] - cacKhoang[chiMucKhoangHienTai][0] + 1;
hangDoiUuTien.push({doDai, cacKhoang[chiMucKhoangHienTai][1]});
}
++chiMucKhoangHienTai;
}
// Bước 2: Loại bỏ các khoảng không còn hợp lệ khỏi hàng đợi ưu tiên.
// Một khoảng không hợp lệ nếu điểm kết thúc của nó nhỏ hơn điểm truy vấn hiện tại.
while (!hangDoiUuTien.empty() && hangDoiUuTien.top().second < diemTruyVan) {
hangDoiUuTien.pop();
}
// Bước 3: Lấy độ dài khoảng ngắn nhất từ hàng đợi.
// Nếu hàng đợi không rỗng, phần tử top chính là khoảng ngắn nhất hợp lệ.
if (!hangDoiUuTien.empty()) {
ketQua[chiMucGoc] = hangDoiUuTien.top().first;
}
}
return ketQua;
}
};
Tiếp cận 3: Sắp xếp các khoảng theo độ dài và loại bỏ truy vấn
Một cách tiếp cận khác là ưu tiên xử lý các khoảng ngắn hơn trước. Nếu một điểm truy vấn được bao phủ bởi một khoảng ngắn, chúng ta có thể ghi nhận kết quả và không cần tìm kiếm thêm cho điểm truy vấn đó nữa.
- Sắp xếp các khoảng giá trị theo độ dài tăng dần.
- Lưu trữ các điểm truy vấn cùng với chỉ mục gốc của chúng trong một
std::multimap.multimapsẽ tự động sắp xếp các truy vấn theo giá trị điểm tăng dần, đồng thời cho phép nhiều truy vấn có cùng giá trị. - Duyệt qua từng khoảng giá trị đã sắp xếp:
- Với mỗi khoảng, xác định điểm bắt đầu, điểm kết thúc và độ dài của nó.
- Sử dụng
multimap::lower_boundđể tìm điểm truy vấn đầu tiên lớn hơn hoặc bằng điểm bắt đầu của khoảng. - Duyệt từ điểm đó trở đi, xử lý tất cả các điểm truy vấn nằm trong khoảng hiện tại (tức là điểm truy vấn nhỏ hơn hoặc bằng điểm kết thúc của khoảng).
- Đối với mỗi điểm truy vấn được xử lý, gán độ dài của khoảng hiện tại vào vị trí kết quả tương ứng và xóa điểm truy vấn đó khỏi
multimap. Việc xóa này đảm bảo rằng mỗi truy vấn chỉ nhận độ dài từ khoảng ngắn nhất chứa nó.
#include <vector>
#include <algorithm>
#include <map> // Cho std::multimap
#include <utility> // Cho std::pair
class XuLyKhoangTheoDoDai {
public:
// Hàm tìm độ dài khoảng ngắn nhất chứa mỗi điểm truy vấn
std::vector<int> timDoDaiKhoangNganNhat(std::vector<std::vector<int>>& dsCacKhoang, std::vector<int>& dsCacTruyVan) {
// Sắp xếp các khoảng theo độ dài tăng dần.
// Khoảng ngắn hơn sẽ được xử lý trước.
std::sort(dsCacKhoang.begin(), dsCacKhoang.end(), [](const std::vector<int>& a, const std::vector<int>& b) {
return (a[1] - a[0]) < (b[1] - b[0]);
});
// Sử dụng multimap để lưu trữ các truy vấn chưa được xử lý.
// Key là giá trị điểm truy vấn, Value là chỉ mục gốc của truy vấn.
// Multimap cho phép lưu nhiều truy vấn có cùng giá trị.
// Nó cũng tự động sắp xếp các truy vấn theo giá trị điểm tăng dần.
std::multimap<int, int> truyVanChuaXuLy;
for (int i = 0; i < dsCacTruyVan.size(); ++i) {
truyVanChuaXuLy.insert({dsCacTruyVan[i], i});
}
// Vector lưu trữ kết quả, khởi tạo với giá trị -1
std::vector<int> ketQua(dsCacTruyVan.size(), -1);
// Duyệt qua từng khoảng đã được sắp xếp theo độ dài
for (const auto& khoangHienTai : dsCacKhoang) {
int diemBatDau = khoangHienTai[0];
int diemKetThuc = khoangHienTai[1];
int doDaiKhoang = diemKetThuc - diemBatDau + 1;
// Tìm kiếm tất cả các truy vấn nằm trong khoảng hiện tại.
// `lower_bound` tìm truy vấn có giá trị >= diemBatDau.
// Duyệt từ đó cho đến khi truy vấn có giá trị > diemKetThuc.
// Đồng thời, gán kết quả và xóa truy vấn khỏi multimap.
// Việc xóa truy vấn ngay lập tức đảm bảo rằng mỗi truy vấn chỉ được xử lý một lần
// và nhận được độ dài từ khoảng *ngắn nhất* chứa nó (vì các khoảng đã được sắp xếp).
for (auto it = truyVanChuaXuLy.lower_bound(diemBatDau);
it != truyVanChuaXuLy.end() && it->first <= diemKetThuc;
/* Không tăng it ở đây, vì erase trả về iterator tiếp theo */)
{
ketQua[it->second] = doDaiKhoang;
it = truyVanChuaXuLy.erase(it); // Xóa truy vấn đã xử lý và lấy iterator tiếp theo
}
}
return ketQua;
}
};