Trộn Danh Sách Chờ Khám Family Medical

Mô tả

Trưa Chủ nhật tại phòng khám Family Medical, hai quầy tiếp đôn A và B cùng lúc chạy nghiệp vụ phát số thứ tự ưu tiên khám bệnh. Mỗi quầy in ra một dải mã số bệnh nhân đã được hệ thống sắp sẵn theo thứ tự ưu tiên tăng dần (số nhỏ hơn được gọi vào phòng khám trước). Giờ phút cao điểm, y tá Lan cần gộp hai dải số này thành một danh sách chờ chung duy nhất, sao cho thứ tự ưu tiên tổng thể vẫn tăng dần và không sót bất kỳ ai.

Nhiệm vụ của bạn là viết chương trình nhận hai danh sách số nguyên đã sắp xếp tăng dần, sau đó trộn chúng lại thành một danh sách duy nhất cũng được sắp xếp tăng dần. Bí quyết ở đây là tận dụng chính tính chất đã sẵn sắp xếp của từng danh sách đầu vào để tránh duyệt lại nhiều lần.

Đầu vào

• Dòng đầu tiên chứa hai số nguyên n và m (0 ≤ n, m ≤ 10^5), lần lượt là số lượng bệnh nhân ở danh sách A và danh sách B.
• Dòng thứ hai chứa n số nguyên của danh sách A, cách nhau bởi khoảng trắng, đã sắp xếp tăng dần.
• Dòng thứ ba chứa m số nguyên của danh sách B, cách nhau bởi khoảng trắng, đã sắp xếp tăng dần.

Đầu ra

• In ra trên một dòng duy nhất danh sách kết quả gồm n + m phần tử đã được trộn và sắp xếp tăng dần. Các số cách nhau bởi một khoảng trắng.

Ràng buộc

• 0 ≤ n, m ≤ 10^5.
• Mỗi phần tử trong danh sách là số nguyên có giá trị tuyệt đối không vượt quá 10^9.
• Tổng số phần tử sau trộn n + m có thể lên tới 200.000.
• Cần giải quyết trong thời gian tuyến tính O(n + m), không được sắp xếp lại toàn bộ từ đầu.

Ví dụ

Ví dụ 1:

• Đầu vào:

3 4 5 10 15 2 6 8 20

• Đầu ra:

2 5 6 8 10 15 20

Giải thích từng bước:

• So sánh phần đầu A[0]=5 và B[0]=2: chọn 2, dịch con trỏ B.
• So sánh 5 và 6: chọn 5, dịch con trỏ A.
• Tiếp tục so sánh từng cặp, mỗi lần chọn số nhỏ hơn.
• Khi một danh sách hết, ta chỉ việc nối toàn bộ phần còn lại của danh sách kia vào kết quả.