Bài toán Số Sân Ga Tối Thiểu

Giới thiệu

Cho danh sách giờ đến và giờ đi của các tàu hỏa. Bài toán yêu cầu tìm số sân ga tối thiểu cần thiết để không tàu nào phải chờ đợi.

Bằng cách sắp xếp tất cả các thời điểm theo thứ tự, ta có thể giải quyết dễ dàng: khi một tàu đến mà chưa có tàu nào đi, ta cần thêm sân ga; khi tàu đi, sân ga được giải phóng.

Độ phức tạp thời gian: O(n log n) do bước sắp xếp.

Đầu vào và Đầu ra

Đầu vào: Danh sách giờ đến và giờ đi.
Giờ đến: {900, 940, 950, 1100, 1500, 1800}
Giờ đi: {910, 1200, 1120, 1130, 1900, 2000}
Đầu ra: Số sân ga tối thiểu cần: 3

Thuật toán

minPlatform(arrival, departure, int n)

Đầu vào: Danh sách giờ đến, giờ đi và số phần tử

Đầu ra: Số sân ga tối thiểu cần thiết

Begin
  sắp xếp danh sách giờ đến và giờ đi
  platform := 1 và minPlatform := 1
  i := 1 và j := 0
  với các phần tử trong danh sách arrival[i] và departure[j] làm:
    nếu arrival[i] < departure[j] thì
      platform := platform + 1
      i := i + 1
      nếu platform > minPlatform thì
        minPlatform := platform
    ngược lại
      platform := platform - 1
      j := j + 1
  done
  trả về minPlatform
End

Ví dụ (C++)

#include <iostream>
#include <algorithm>
using namespace std;

int minPlatform(int arrival[], int departure[], int n) {
  sort(arrival, arrival + n);   // sắp xếp giờ đến và giờ đi
  sort(departure, departure + n);
  int platform = 1, minPlatform = 1;
  int i = 1, j = 0;
  while (i < n && j < n) {
    if (arrival[i] < departure[j]) {
      platform++;  // thêm sân ga
      i++;
      if (platform > minPlatform)  // cập nhật minPlatform nếu cần
        minPlatform = platform;
    } else {
      platform--;  // giải phóng sân ga
      j++;
    }
  }
  return minPlatform;
}

int main() {
  int arrival[] = {900, 940, 950, 1100, 1500, 1800};
  int departure[] = {910, 1200, 1120, 1130, 1900, 2000};
  int n = 6;
  cout << "Minimum Number of Platforms Required: " << minPlatform(arrival, departure, n);
}

Kết quả đầu ra

Minimum Number of Platforms Required: 3