Asked Jun 22nd, 2:55 AM 131 2 1
  • 131 2 1
+1

Nhờ mọi người giúp đỡ về thuật toán trong bài toán Booking ạ

Share
  • 131 2 1

Đề bài: Book phòng hát karaoke
Quán sẽ mở cửa từ 9:00 đến 23:00.

  • Input: User sẽ nhập vào thông tin: Date, StartTime, EndTime
  • Output: Kiểm tra xem với thời thời gian khách hạng booking, thì có phòng nào trống hay ko.
    Nếu có thì trả về true.
    Nếu không thì trả về các khung giờ mà khách có thể booking

Ví dụ 1:
Input:

  • Date: 2021/07/01
  • StartTime: 9:00
  • EndTime: 10:00

Output: true

Ví dụ 2:
Input:

  • Date: 2021/07/01
  • StartTime: 10:00
  • EndTime: 12:00

Output:

[
      [from: 9:00, to: 10:30],
      [from: 11:30, to: 13:00],
      [from: 14:00, to: 16:00],
      [from: 17:30, to: 23:00],
]

1 ANSWERS


Answered Jun 22nd, 8:01 AM
Accepted
+5

Bạn thử xem cách sau có ổn không nhé:

  • Giả sử đang cần kiểm tra ca thông tin có date, startTimeendTime
  • Đầu tiên check startTimeendTime có nằm trong thời gian mở cửa của cửa hàng không. Nếu không thì báo là false luôn.
  • Select ra các ca đã book phòng trong cùng ngày, sort theo startTime, lưu vào biến bookings
  • Chạy một vòng for qua các booking, nếu startTime hoặc endTime mà nằm trong khoảng booking.startTimebooking.endTime, hoặc booking.startTimebooking.endTime nằm trong khoảng giữa startTimeendTime, thì tức là thời gian đó đã bị đè vào lịch nào đó được book rồi. Lúc này ta chỉ cần return false.
  • Nếu chạy qua hết vòng lặp mà không bị return false thì chứng tỏ thời gian đó không bị trùng với booking nào cả => có thể book được vào khung giờ đó.

Dưới đây là đoạn code đơn giản bằng Javascript, bạn có thể tham khảo xem sao

// openTime và endTime là thời gian mở và đóng cửa hàng
// bookings là mảng các booking
// startTime và endTime là thời gian đang check xem có còn trống không
function check(openTime, closeTime, bookings, startTime, endTime) {
    if (startTime < openTime || endTime > closeTime) {
        return false;
    }

    for(booking of bookings) {
        if ((startTime >= booking.startTime && startTime < booking.endTime)
        || (endTime > booking.startTime && endTime < booking.endTime)
        || (startTime < booking.startTime && endTime >= booking.endTime)
        ) {
            return false;
        }
    }

    return true;
}

// Hàm get danh sách những khung giờ còn trống
// Một khung giờ còn trống là khoảng thời gian từ endTime của một booking, đến startTime của booking tiếp theo
function getAvailableTime(openTime, closeTime, bookings) {
    lastEndTime = openTime;
    availableTime = [];
    for(booking of bookings) {
        if (booking.startTime > lastEndTime) {
            availableTime.push([lastEndTime, booking.startTime]);
        }
        lastEndTime = booking.endTime;
    }
    availableTime.push([lastEndTime, closeTime]);
    return availableTime;
}

bookings = [
    {
        startTime: 10.5,
        endTime: 11.5
    },
    {
        startTime: 13,
        endTime: 14
    },
    {
        startTime: 14,
        endTime: 15,
    },
    {
        startTime: 16,
        endTime: 17.5
    }
];

openTime = 9;
endTime = 23;
avalableTime = getAvailableTime(openTime, endTime, bookings);

isTimeValid = check(openTime, endTime, bookings, 9, 10); // true
if (!isTimeValid) {
    console.log(availableTime);
}

isTimeValid = check(openTime, endTime, bookings, 10, 12); // false
if (!isTimeValid) {
    console.log(availableTime);
}
Share
Avatar iamfresher @benkyou
Jun 22nd, 10:19 AM

@thangtd90
E cảm ơn anh đã dành thời gian cho câu hỏi của em ạ.

Đoạn check điều kiện bên trên, e nghĩ chắc phải thêm 1 điều kiện nữa.
Vì với 3 điều kiện hiện tại em thấy có vẻ như bị lack 1 trường hợp.
A thấy ổn ko ạ?

if ((startTime >= booking.startTime && startTime < booking.endTime)
        || (endTime > booking.startTime && endTime < booking.endTime)
        || (startTime < booking.startTime && endTime >= booking.endTime)
        || (startTime == booking.startTime && endTime == booking.endTime)
        ) {
            return false;
        }
0
| Reply
Share
Avatar Tran Duc Thang @thangtd90
Jun 22nd, 10:50 AM

@benkyou Anh thấy cái này startTime == booking.startTime && endTime == booking.endTime thì nằm trong cái điều kiện thứ nhất là startTime >= booking.startTime && startTime < booking.endTime rồi mà nhỉ 😄 (mình mặc định điều kiện hiển nhiên là booking.startTime < booking.endTime)

À mà chắc là mình có thể viết lại thế này cho dễ hiểu hơn em ạ

if (!(endTime <= booking.startTime || startTime >= booking.endTime)) {
    return false;
}

Tức một khoảng thời gian là hợp lệ nếu endTime của nó nhỏ hơn hoặc bằng startTime của booking đã có, hoặc startTime của nó lớn hơn hoặc bằng endTime của booking đã có 🤔

+1
| Reply
Share
Avatar iamfresher @benkyou
Jun 22nd, 1:07 PM

@thangtd90

Anh thấy cái này startTime == booking.startTime && endTime == booking.endTime thì nằm trong cái điều kiện thứ nhất là startTime >= booking.startTime && startTime < booking.endTime rồi mà nhỉ

Dạ, đúng như a nói rồi. lúc lẫy em hơi rối 😄

0
| Reply
Share
Avatar iamfresher @benkyou
Jun 22nd, 1:14 PM

À mà chắc là mình có thể viết lại thế này cho dễ hiểu hơn em ạ

if (!(endTime <= booking.startTime || startTime >= booking.endTime)) {
    return false;
}

Tức một khoảng thời gian là hợp lệ nếu endTime của nó nhỏ hơn hoặc bằng startTime của booking đã có, hoặc startTime của nó lớn hơn hoặc bằng endTime của booking đã có

E cảm ơn anh nhiều ạ. A viết ra rồi thì nhìn đúng là nó đơn giản thật, mà lúc làm thì khó nghĩ ra đc 😄

0
| Reply
Share
Avatar iamfresher @benkyou
Jun 22nd, 1:23 PM

tiện thể em cũng xin memo lại các làm hiện tại của em luôn ạ.

Bước 1: em dùng truy vấn Sql để lấy ra các khoảng thời gian available cho booking.

$availableRanges = 
SELECT cast(available_from AS DECIMAL(10,2)) AS available_from, (CONVERT(available_to, DECIMAL(10,2)) - 0.5) AS available_to
        FROM (        
            SELECT 
                @lasttime_to AS available_from,
                start_time_decimal  AS available_to,
                @lasttime_to := re_available_time_decimal 
            FROM (
                    (SELECT * FROM reservations 
                    WHERE reservation_date = "{$day}" AND room_id={$roomId}
                    ORDER BY start_time_decimal, re_available_time_decimal) AS origin
                    JOIN (SELECT @lasttime_to := 9) AS init
                )
            UNION
            SELECT @lasttime_to AS available_from,
                21   AS available_to,
                0
            ) AS result
WHERE result.available_from <> result.available_to

Bước 2: Loop qua các khung thời gian available và check xem startTime và endTime có thuộc khoảng đang available hay không.

foreach ($roomAvailableRanges as $item) {
    if ( ($item->available_from <= $startTime && $startTime   <= $item->available_to) 
    && ($item->available_from <= $endTime  && $endTime    <= $item->available_to)
     ) {
         return true;
     }
     return $roomAvailableRanges ;
 }
0
| Reply
Share
Viblo
Let's register a Viblo Account to get more interesting posts.