Giới thiệu

Chào bạn! Tôi là Asparagos - một cây măng tây biết lập trình bằng Go. Trong bài viết này, chúng ta sẽ cùng nhau khám phá một bài toán thú vị mà các loại rau củ có thể gặp phải trong cuộc sống hàng ngày - đó là bài toán Cứu Táo 🍎.

Mỗi mùa, táo lại phải tìm cách trốn khỏi những chiếc bánh táo (apple pie) để tìm một nơi an toàn hơn. Liệu một chiếc tàu hỏa có thể cứu tất cả táo mà không vượt quá số ghế của nó không?

Bài toán

Mùa bánh táo đã bắt đầu, và tất cả các quả táo đang rời khỏi nhà của chúng để tìm kiếm một nơi an toàn hơn. Không ai muốn trở thành nguyên liệu cho một chiếc bánh nữa — điều đó đã quá lỗi thời. Một ly sinh tố có vẻ tốt hơn, hoặc ít nhất là một chiếc strudel.

Có một chiếc tàu hỏa đi theo một hướng với số ghế hạn chế. Các quả táo di chuyển thành nhóm: mỗi nhóm muốn lên tàu tại điểm X và rời khỏi tại điểm Y.

Liệu chiếc tàu có thể đưa tất cả táo mà không vượt quá số ghế của nó không?

Đầu vào 🍐

trips []Trip: thông tin về các chuyến đi theo nhóm. Mỗi Trip bao gồm một điểm khởi hành from, một điểm dừng to, và kích thước nhóm num.
capacity int: số lượng ghế trên tàu.

Đầu ra 🍊

Trả về true nếu tàu có thể chở tất cả táo mà không vượt quá sức chứa tại bất kỳ thời điểm nào; false nếu không.

Ví dụ 🍋

Ví dụ 1

Đầu vào: trips = {{from: 2, to: 7, num: 1}, {from: 0, to: 2, num: 3}, {from: 1, to: 3, num: 2}}, capacity = 5

Đầu ra: true

Ở điểm 0, tàu chở 3 quả táo.

Sau đó, ở điểm 1, tàu chở thêm 2 quả táo, vậy là tất cả 5 ghế đã được lấp đầy.

Ở điểm 2, 3 quả táo rời khỏi tàu. Đồng thời, 1 quả táo lên tàu. Giờ đây, có 3 quả táo trên tàu.

Ở điểm 3, 2 quả táo rời khỏi tàu. Chỉ còn lại 1 quả táo, sẽ rời khỏi tại điểm 7.

Số táo trên tàu không bao giờ vượt quá sức chứa của tàu.
Ví dụ 2

Đầu vào: trips = {{from: 0, to: 2, num: 3}, {from: 1, to: 3, num: 2}}, capacity = 4

Đầu ra: false

Ở điểm 0, tàu chở 3 quả táo.

Ở điểm 1, tàu cần chở thêm 2 quả táo. Điều này sẽ yêu cầu 5 ghế, nhưng sức chứa chỉ có 4, vì vậy tàu không thể chở chúng.

Giải pháp 💡

Chúng ta sẽ thực hiện các bước sau:

Xây dựng danh sách sự kiện: Mỗi chuyến đi sẽ tạo ra một sự kiện đón tại from và một sự kiện trả tại to. Chúng ta sẽ sắp xếp các sự kiện theo vị trí tăng dần. Khi hai sự kiện có cùng một vị trí, sự kiện trả sẽ được xử lý trước sự kiện đón. Điều này cho phép số ghế trống được sử dụng ngay lập tức. Mỗi sự kiện sẽ bao gồm: location, num (kích thước nhóm), và isFrom (liệu đây có phải là sự kiện đón hay không).
Duyệt qua các sự kiện: Chúng ta sẽ lặp qua các events và cập nhật số lượng táo hiện có trên tàu num. Nếu là sự kiện trả, chúng ta sẽ trừ kích thước nhóm từ num. Ngược lại, chúng ta sẽ cộng kích thước nhóm vào num.
Kiểm tra sức chứa: Nếu tại bất kỳ thời điểm nào, việc đón thêm nhóm táo sẽ vượt quá sức chứa, trả về false. Nếu không, trả về true.

go Copy

type Trip struct {
    from int
    to   int
    num  int
}

type Event struct {
    location int
    num      int
    isFrom   bool
}

func canSaveAllApples(trips []Trip, capacity int) bool {
    events := make([]Event, 0, 2*len(trips))
    for _, trip := range trips {
        events = append(events, Event{trip.from, trip.num, true}, Event{trip.to, trip.num, false})
    }
    slices.SortFunc(events, func(a, b Event) int {
        if a.location != b.location {
            return cmp.Compare(a.location, b.location)
        }
        if a.isFrom == b.isFrom {
            return 0
        }
        if !a.isFrom {
            return -1
        }
        return 1
    })
    num := 0
    for _, event := range events {
        if !event.isFrom {
            num -= event.num
            continue
        }
        if capacity-num < event.num {
            return false
        }
        num += event.num
    }
    return true
}

Các thực tiễn tốt nhất

Kiểm tra đầu vào: Đảm bảo rằng các đầu vào cho hàm canSaveAllApples là hợp lệ và không chứa giá trị âm.
Tối ưu hóa bộ nhớ: Sử dụng một cấu trúc dữ liệu phù hợp để tiết kiệm bộ nhớ khi xử lý nhiều chuyến đi.

Những cạm bẫy thường gặp

Không xử lý đúng trường hợp rỗng: Đảm bảo kiểm tra trường hợp không có chuyến đi nào được cung cấp.
Quá tải sức chứa: Luôn kiểm tra sức chứa trước khi thêm táo mới vào tàu.

Mẹo hiệu suất

Sắp xếp sự kiện một cách hiệu quả: Sử dụng thuật toán sắp xếp nhanh hoặc tối ưu cho danh sách sự kiện để giảm thời gian xử lý.

Giải quyết sự cố

Lỗi sức chứa: Nếu hàm trả về false, hãy kiểm tra lại các chuyến đi và sức chứa để xác định lý do.

Kết luận

Bài toán Cứu Táo không chỉ là một thử thách thú vị mà còn giúp chúng ta hiểu sâu hơn về cách xử lý các sự kiện trong lập trình Go. Hãy thử nghiệm với mã nguồn và đóng góp ý kiến của bạn trên GitHub! Nếu bạn thấy bài viết này hữu ích, đừng ngần ngại để lại một ⭐ nhé!

Giải quyết bài toán Cứu Táo bằng Go