Minimum Platforms

Q: Độ phức tạp thời gian của bài toán số sân ga tối thiểu là bao nhiêu?

Việc sắp xếp hai mảng tốn O(n log n) , còn bước quét sau đó tốn O(n) , nên phần sắp xếp chiếm ưu thế. Các bản sao đã sắp xếp cần thêm O(n) bộ nhớ.

Q: Minimum platforms khác với meeting rooms II như thế nào?

Cả hai bài toán đều tìm số khoảng thời gian chồng lấn nhiều nhất tại cùng một thời điểm. Ở đây, một chuyến tàu chiếm sân ga trong suốt phút tàu rời đi; còn ở bài toán meeting rooms II, một phòng trống ngay khi cuộc họp kết thúc. Trong quá trình quét, đây là một phép so sánh: nếu hai thời điểm trùng nhau, ở đây bạn xử lý lượt đến trước, còn ở bài toán kia, bạn xử lý cuộc họp kết thúc trước.

Q: Có thể giải bài toán số sân ga tối thiểu mà không cần sắp xếp không?

Đúng vậy, vì mỗi thời điểm đều khớp với một mốc giờ cố định. Đánh chỉ số cho 2401 bộ đếm bằng số HHMM , tăng 1 tại mỗi thời điểm đến và giảm 1 tại departure + 1 . Tổng tích lũy lớn nhất là đáp án: thời gian O(n + 2400) . Các chỉ số như 1260 đến 1299 không phải là giờ hợp lệ nên không có lượt đến nào, vì vậy chúng không bao giờ tạo ra mức cao nhất.

Trung bìnhSắp xếp Tham lam Hai con trỏ

+10

Một nhà ga có lịch trình trong một ngày: tàu i đến vào lúc arrival[i] và rời đi vào lúc departure[i]. Thời gian là các số HHMM, tức giờ trên đồng hồ không có dấu hai chấm, nên 930 là 09:30.

Một đoàn tàu chiếm sân ga từ phút đến cho đến phút rời đi, tính cả hai phút này. Vì vậy, tàu đến đúng phút một tàu khác rời đi không thể dùng sân ga của tàu đó.

Hãy trả về số sân ga ít nhất mà nhà ga cần để không có tàu nào phải chờ.

Hàm

minimumPlatforms(arrival: integer-array, departure: integer-array) → integer

arrivalinteger-array: thời gian đến của mỗi chuyến tàu, dưới dạng số HHMM
departureinteger-array: thời gian khởi hành của mỗi chuyến tàu, dưới dạng số HHMM; departure[i] tương ứng với arrival[i]
Trả vềinteger: số lượng tàu lớn nhất ở nhà ga trong cùng một phút, tức là số sân ga ít nhất cần có

Ràng buộc

1 ≤ arrival.length == departure.length ≤ 5000
0 ≤ arrival[i] ≤ departure[i] ≤ 2359
Mỗi thời điểm đều có định dạng HHMM hợp lệ: hai chữ số cuối cùng không vượt quá 59.
Tất cả các chuyến tàu đều chạy trong cùng một ngày. Các mảng chưa được sắp xếp.

Ví dụ

Đầu vào: arrival = [900, 1500, 920, 1520, 1000, 1530]departure = [930, 1600, 1010, 1535, 1100, 1545]
Đầu ra: 3
Giải thích: Lúc 15:30, có ba chuyến tàu đang ở nhà ga: chuyến từ 15:00 đến 16:00, chuyến từ 15:20 đến 15:35 và chuyến từ 15:30 đến 15:45. Không có phút nào có bốn chuyến tàu, nên 3 sân ga là đủ.

Đầu vào: arrival = [1200, 1230, 1300]departure = [1230, 1300, 1315]
Đầu ra: 2
Giải thích: Chuyến tàu đến lúc 12:30 gặp chuyến tàu rời đi lúc 12:30, và điều tương tự xảy ra lúc 13:00. Vào mỗi thời điểm đó, có hai chuyến tàu ở nhà ga, nên đáp án là 2, không phải 1.

Đầu vào: arrival = [600, 700, 1300]departure = [2200, 715, 1400]
Đầu ra: 2
Giải thích: Chuyến tàu từ 06:00 đến 22:00 khiến một sân ga luôn bận rộn cả ngày. Các chuyến tàu từ 07:00 đến 07:15 và từ 13:00 đến 14:00 không bao giờ gặp nhau, nên chúng dùng chung sân ga thứ hai: 2.

Câu hỏi mở rộng

Một số chuyến tàu đêm đến trước nửa đêm và khởi hành sau nửa đêm, nên số giờ khởi hành nhỏ hơn số giờ đến. Bạn sẽ đếm số sân ga như thế nào khi lịch trình vượt qua nửa đêm?

Lời giải

Đáp án là số lượng tàu lớn nhất có mặt tại nhà ga trong cùng một phút. Bài toán là tìm phút đông tàu nhất mà không cần so sánh từng cặp tàu. Hãy sắp xếp riêng thời điểm tàu đến và rời đi, rồi duyệt qua các sự kiện trong ngày một lần, cập nhật số lượng tàu liên tục để tìm ra đáp án trong O(n log n).

Đếm số đoàn tàu đến tại mỗi ga

Đúng, nhưng không chạy xong với các test lớn nhất

Ý tưởng

Các đoàn tàu đứng trên sân ga trong cùng một phút đều cần sân ga riêng, vì vậy phút bận rộn nhất là giới hạn dưới. Mức đó cũng đủ: chỉ mở sân ga mới khi một đoàn tàu đến và thấy tất cả sân ga đang mở đều có tàu. Trong phút đó, mỗi sân ga đang mở có một đoàn tàu đứng, cộng thêm đoàn tàu mới, vì vậy bạn không bao giờ mở nhiều sân ga hơn mức cao điểm.

Số đoàn tàu có mặt chỉ tăng khi có tàu đến, vì vậy phút bận rộn nhất là phút đến của một đoàn tàu nào đó. Với mỗi đoàn tàu i, hãy đếm số đoàn tàu j thỏa mãn arrival[j] ≤ arrival[i] ≤ departure[j]. Cả hai phép so sánh đều dùng ≤ vì đoàn tàu vẫn đứng trên sân ga trong phút nó rời đi.

Mỗi trong số n đoàn tàu kiểm tra tất cả n đoàn tàu, nên khối lượng công việc là O(n²): 25 triệu phép kiểm tra cặp với 5000 đoàn tàu.

Thuật toán

Đặt most = 0.
Với mỗi chuyến tàu i, đếm số chuyến tàu j thỏa mãn arrival[j] ≤ arrival[i] ≤ departure[j].
Nếu số đếm đó lớn hơn most, hãy lưu lại số đó.
Trả về most.

def minimumPlatforms(arrival, departure):
    n = len(arrival)
    most = 0
    for i in range(n):
        # trains standing at the station in the minute train i arrives
        here = 0
        for j in range(n):
            if arrival[j] <= arrival[i] <= departure[j]:
                here += 1
        most = max(most, here)
    return most

Sắp xếp cả hai danh sách rồi duyệt bằng hai con trỏ

Ý tưởng

Số lượng tàu có mặt chỉ phụ thuộc vào số tàu đã đến và số tàu đã rời đi tính đến một phút nhất định, chứ không phụ thuộc vào việc tàu nào rời đi lúc nào. Vì vậy, hãy sắp xếp thời gian đến và thời gian rời đi thành hai danh sách riêng biệt. Khi đọc theo thứ tự thời gian, chúng tạo thành các sự kiện trong ngày: một lượt đến làm tăng số tàu, một lượt rời đi làm giảm số tàu.

Nếu hai sự kiện trùng thời điểm, lượt đến được tính trước, vì tàu sắp rời đi vẫn chiếm sân ga trong phút đó. Trong ví dụ đầu tiên, số tàu giảm về 0 sau lượt rời đi lúc 1100, sau đó các lượt đến lúc 1500, 1520 và 1530 đều diễn ra trước lượt rời đi lúc 1535, nên số tàu tăng lên 3.

Khi không còn lượt đến nào, các lượt rời đi còn lại chỉ có thể làm giảm số tàu, nên quá trình duyệt dừng tại đó. Việc sắp xếp tốn O(n log n) và quá trình duyệt mất nhiều nhất 2n bước.

Thuật toán

Sắp xếp một bản sao của arrival và một bản sao của departure.
Đặt platforms, most, i và j thành 0.
Khi i < n: nếu arrivals[i] ≤ departures[j], tăng platforms thêm 1, cập nhật most rồi tăng i.
Nếu không, giảm platforms đi 1 rồi tăng j.
Trả về most.

def minimumPlatforms(arrival, departure):
    arrivals = sorted(arrival)
    departures = sorted(departure)
    n = len(arrivals)
    platforms = 0  # trains at the station right now
    most = 0
    i = 0  # next arrival
    j = 0  # next departure
    while i < n:
        if arrivals[i] <= departures[j]:
            # the next event is an arrival; on a tie the leaving train is still there
            platforms += 1
            most = max(most, platforms)
            i += 1
        else:
            platforms -= 1
            j += 1
    return most

Lỗi thường gặp và trường hợp biên

So sánh bằng < khi quy tắc bao gồm cả giá trị bằng cần dùng ≤. Trong ví dụ thứ hai, mỗi chuyến tàu đến sau đó dùng sân ga của chuyến tàu rời đi vào đúng phút đó, và đáp án giảm từ 2 xuống 1.
Trừ các số HHMM: 1300 trừ 1259 bằng 41, dù hai thời điểm chỉ cách nhau một phút. So sánh chúng thì an toàn, và lời giải chỉ thực hiện phép so sánh.
Sắp xếp các chuyến tàu theo giờ đến rồi chỉ so sánh mỗi chuyến với chuyến ngay trước nó. Thời gian dừng lâu như từ 06:00 đến 22:00 trong ví dụ thứ ba sẽ trùng với các chuyến tàu ở xa hơn trong danh sách.
Bỏ qua các chuyến tàu đến và rời đi trong cùng một phút. Bốn chuyến tàu, mỗi chuyến dừng từ 10:00 đến 10:00, cần bốn sân ga.

Câu hỏi thường gặp3

Độ phức tạp thời gian của bài toán số sân ga tối thiểu là bao nhiêu?

Việc sắp xếp hai mảng tốn O(n log n), còn bước quét sau đó tốn O(n), nên phần sắp xếp chiếm ưu thế. Các bản sao đã sắp xếp cần thêm O(n) bộ nhớ.

Minimum platforms khác với meeting rooms II như thế nào?

Cả hai bài toán đều tìm số khoảng thời gian chồng lấn nhiều nhất tại cùng một thời điểm. Ở đây, một chuyến tàu chiếm sân ga trong suốt phút tàu rời đi; còn ở bài toán meeting rooms II, một phòng trống ngay khi cuộc họp kết thúc. Trong quá trình quét, đây là một phép so sánh: nếu hai thời điểm trùng nhau, ở đây bạn xử lý lượt đến trước, còn ở bài toán kia, bạn xử lý cuộc họp kết thúc trước.

Có thể giải bài toán số sân ga tối thiểu mà không cần sắp xếp không?

Đúng vậy, vì mỗi thời điểm đều khớp với một mốc giờ cố định. Đánh chỉ số cho 2401 bộ đếm bằng số HHMM, tăng 1 tại mỗi thời điểm đến và giảm 1 tại departure + 1. Tổng tích lũy lớn nhất là đáp án: thời gian O(n + 2400). Các chỉ số như 1260 đến 1299 không phải là giờ hợp lệ nên không có lượt đến nào, vì vậy chúng không bao giờ tạo ra mức cao nhất.

def minimumPlatforms(arrival, departure):
    # Viết code tại đây

Kiểm thử #1

Kiểm thử #2

Kiểm thử #3

Đối số

arrival = [900, 1500, 920, 1520, 1000, 1530]
departure = [930, 1600, 1010, 1535, 1100, 1545]

Đầu ra mong đợi