Chương trình tìm phòng gần nhất từ truy vấn trong Python

Cho mảng rooms với rooms[i] = [roomId_i, size_i] và mảng queries với queries[j] = [preferred_j, minSize_j]. Cần tìm roomId thỏa: (1) size ≥ minSize_j, (2) |id - preferred_j| nhỏ nhất. Nếu tie, lấy id nhỏ hơn. Nếu không có, trả -1.

Ví dụ: rooms = [[2,2],[1,2],[3,2]], queries = [[3,1],[3,3],[5,2]] → output = [3, -1, 3].

Giải thuật (Sort + Binary Search)

• Sắp xếp rooms theo size tăng, tie-break theo id.
• Sắp xếp queries theo minSize giảm dần.
• Duyệt queries: thêm các room đủ size vào danh sách X (giữ sorted bằng bisect.insort).
• Với preferred_j, dùng bisect.bisect tìm vị trí chèn trong X, so sánh X[j] và X[j-1] để lấy id gần nhất.

Code Python

import bisect

def solve(rooms, queries):
    rooms.sort(key=lambda x: (x[1], x[0]))
    queries = [(qid, size, i) for i, (qid, size) in enumerate(queries)]
    queries.sort(key=lambda x: (x[1], x[0], x[2]), reverse=True)
    ans = [-1] * len(queries)
    X = []
    for qid, size, i in queries:
        while rooms and rooms[-1][1] >= size:
            idr, _ = rooms.pop()
            bisect.insort(X, idr)
        if X:
            j = bisect.bisect(X, qid)
            if j == len(X):
                ans[i] = X[-1]
            elif j == 0:
                ans[i] = X[0]
            else:
                ans[i] = X[j] if X[j] - qid < qid - X[j-1] else X[j-1]
    return ans

rooms = [[2,2],[1,2],[3,2]]
queries = [[3,1],[3,3],[5,2]]
print(solve(rooms, queries))  # [3, -1, 3]

Đầu vào / Đầu ra

Input: [[2,2],[1,2],[3,2]], [[3,1],[3,3],[5,2]]
Output: [3, -1, 3]