+1
Nhờ mọi người giúp đỡ về thuật toán trong bài toán Booking ạ
Đề 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],
]
Thêm một bình luận
1 CÂU TRẢ LỜI
+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,startTimevàendTime - Đầu tiên check
startTimevàendTimecó 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àfalseluô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
forqua cácbooking, nếustartTimehoặcendTimemà nằm trong khoảngbooking.startTimevàbooking.endTime, hoặcbooking.startTimevàbooking.endTimenằm trong khoảng giữastartTimevàendTime, 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 returnfalse. - 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);
}
@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;
}
@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ó 
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
À 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
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 ;
}
