Thuật toán kiểm tra nhiều khoảng thời gian có bị trùng lặp hay không?

Xin chào tất cả các bạn, mình là Quân, hôm nay chúng ta sẽ cùng nhau tìm hiểu một thuật toán mà mình từng sử dụng trong một dự án thực tế cho khách hàng Nhật, nghe tên thì đơn giản nhưng cũng không kém phần hack não đối với bạn nào mới đụng đến nhé. Đó là thuật toán kiểm tra xem 2 khoảng thời gian có bị trùng lặp (overlapping datetime ranges) hay không?

“Bài này nằm trong loạt bài Kỹ thuật xử lý Javascript nâng cao (đang cập nhật) trên trang blog chính thức trungquandev.com“

Những nội dung có trong bài:

1. Tản mạn phân tích bài toán
2. Code demo với Javascript
3. Full source code trên Github

---

1. Tản mạn phân tích bài toán

À thì cho phép mình tranh thủ tản mạn lý do có bài viết này xuất hiện chút xíu nhé. Vào một ngày đẹp trời khi mình còn làm việc ở dự án cũ, là một dự án của Nhật làm về quản lý đăng ký các ca việc part-time cho nhân viên.

Spec cũ của dự án là mỗi nhân viên chỉ được phép đăng ký tối đa duy nhất 1 ca việc/ngày, nhưng do dự án đang phát triển và mở rộng thêm nên cần đổi lại spec cho phép các nhân viên có thể đăng ký nhiều ca việc trong ngày, với điều kiện là các ca việc đó không bị trùng lặp thời gian.

Và thế là mình loay hoay tìm hiểu về cái thuật toán xử lý trùng lặp khoảng thời gian (overlap time ranges), nói là “thuật toán” cho cao siêu chứ thực ra cũng chỉ đơn giản là một cách xử lý logic thôi ấy mà 😀

Ok tản mạn lý do thế đủ rồi, mình sẽ phân tích logic của việc xử lý overlap datetime ranges này theo một cách cực kỳ dễ hiểu cho các bạn, hãy xem ảnh mình tự vẽ bên dưới đây nhé:

Với 2 trường hợp mình đã phân tích ở hình trên, các bạn để ý chữ mình bôi đỏ nhé, bây giờ chỉ cần đơn giản chúng ta sẽ kết hợp 2 trường hợp đó lại với điều kiện && là sẽ biết được 2 khoảng thời gian A và B có bị trùng lặp hay không. Cụ thể:

(StartA < EndB) && (EndA > StartB)

Khá là đơn giản phải không, nhưng mình đảm bảo nghĩ đi nghĩ lại cũng phải một lúc thì các bạn mới cảm thấy điều kiện trên kia là hợp lý đấy =)))

Tiếp theo trong phần 2, mình sẽ ứng dụng thuật toán trên vào lập trình nhé, cụ thể mình sẽ sử dụng Javascript, các bạn có thể áp dụng vào bất kỳ ngôn ngữ lập trình nào cũng được.

(Ngoài lề quen thuộc: Cảnh báo này dành cho mấy bạn admin của mấy trang TopDev, TechBlog chuyên đi copy rồi xào bài, hoặc bất kể trang nào khác mà đã đi copy bài không phải của các bạn thì hãy tôn trọng người viết, tuyệt đối không được xào nấu bài viết của mình, cấm xóa những liên kết (link) trong bài của mình cũng như tự ý xóa linh tinh các câu thoại của mình trong bài viết, từ giờ nếu mình để ý phát hiện ra nữa thì cứ đơn giản là chắc chắn sẽ ăn report DMCA nhé.)

---

2. Code demo với Javascript

Dựa vào spec và giải pháp đã phân tích ở phần 1, mình sẽ viết lại thành một file code duy nhất như sau:

/**
 * Created by trungquandev.com's author on 09/06/2020.
 * main.js
 */

/**
 * - Function check overlap giữa 2 khoảng thời gian
 * Input:
 * @param {*} incommingDateTimeRange {start: number, end: number}
 * @param {*} existingDateTimeRange {start: number, end: number}
 * 
 * Output:
 * - Boolean: true or false
 */
function areTwoDateTimeRangesOverlapping(incommingDateTimeRange, existingDateTimeRange) {
  return incommingDateTimeRange.start < existingDateTimeRange.end && incommingDateTimeRange.end > existingDateTimeRange.start
}

/**
 * - Function check overlap giữa nhiều khoảng thời gian
 * Input:
 * @param {*} incommingDateTimeRange {start: number, end: number}
 * @param {*} existingDateTimeRanges [{start: number, end: number}, {start: number, end: number}]
 * 
 * Output:
 * - Boolean true or false
 */
function areManyDateTimeRangesOverlapping(incommingDateTimeRange, existingDateTimeRanges) {
  return existingDateTimeRanges.some((existingDateTimeRange) => areTwoDateTimeRangesOverlapping(incommingDateTimeRange, existingDateTimeRange))
}

// Tạo data để test 2 function trên:

/** Date Range A: Thứ 3 ngày 09 tháng 6 năm 2020 lúc 14h đến 14h30 chiều */
const startDateTimeRangeA = new Date('Tue Jun 09 2020 14:00:00 GMT+0700 (Indochina Time)')
const endDateTimeRangeA = new Date('Tue Jun 09 2020 14:30:00 GMT+0700 (Indochina Time)')
const dateTimeRangeA = {
  start: startDateTimeRangeA.getTime(),
  end: endDateTimeRangeA.getTime()
}
/** Date Range B: Thứ 3 ngày 09 tháng 6 năm 2020 lúc 15h đến 15h30 chiều */
const startDateTimeRangeB = new Date('Tue Jun 09 2020 15:00:00 GMT+0700 (Indochina Time)')
const endDateTimeRangeB = new Date('Tue Jun 09 2020 15:30:00 GMT+0700 (Indochina Time)')
const dateTimeRangeB = {
  start: startDateTimeRangeB.getTime(),
  end: endDateTimeRangeB.getTime()
}
/** Date Range C: Thứ 3 ngày 09 tháng 6 năm 2020 lúc 15h30 đến 16h00 chiều */
const startDateTimeRangeC = new Date('Tue Jun 09 2020 15:30:00 GMT+0700 (Indochina Time)')
const endDateTimeRangeC = new Date('Tue Jun 09 2020 16:00:00 GMT+0700 (Indochina Time)')
const dateTimeRangeC = {
  start: startDateTimeRangeC.getTime(),
  end: endDateTimeRangeC.getTime()
}
/** Date Range D: Thứ 3 ngày 09 tháng 6 năm 2020 lúc 15h45 đến 17h00 chiều */
const startDateTimeRangeD = new Date('Tue Jun 09 2020 15:45:00 GMT+0700 (Indochina Time)')
const endDateTimeRangeD = new Date('Tue Jun 09 2020 17:00:00 GMT+0700 (Indochina Time)')
const dateTimeRangeD = {
  start: startDateTimeRangeD.getTime(),
  end: endDateTimeRangeD.getTime()
}

// Kiểm tra A với B: kết quả sẽ không overlap
const checkAB = areTwoDateTimeRangesOverlapping(dateTimeRangeA, dateTimeRangeB)
console.log(`* A và B có overlap không? => ${checkAB}`) // Expected output: false

// Kiểm tra C với D: sẽ bị overlap vì trùng một điểm biên 14h30 (tuỳ vào spec mà các bạn có thể lấy tuyệt đối điểm biên độ hoặc không bằng cách thay dấu lớn hơn thành lớn hơn hoặc bằng trong function)
const checkCD = areTwoDateTimeRangesOverlapping(dateTimeRangeC, dateTimeRangeD)
console.log(`* C và D có overlap không? => ${checkCD}`) // Expected output: true

// Kiểm tra D với [A, B, C]: sẽ bị overlap ở 2 khoảng D với C
const checkABCD = areManyDateTimeRangesOverlapping(dateTimeRangeD, [dateTimeRangeA, dateTimeRangeB, dateTimeRangeC])
console.log(`* 4 khoảng A, B, C và D có overlap không? => ${checkABCD}`) // Expected output: true
//

Code ở trên cũng không có gì phức tạp cả, các bạn để ý cho mình 2 functions:

• areTwoDateTimeRangesOverlapping: dùng để kiểm tra 2 khoảng thời gian có bị overlap hay không theo spec như đã phân tích ở phần 1.
• areManyDateTimeRangesOverlapping: kiểm tra nhiều khoảng thời gian có bị overlap hay không bằng cách dùng vòng lặp và gọi lại hàm check 2 khoảng thời gian ở trên.
  
  – Có một lưu ý trong hàm này là tại sao mình lại dùng Array.some() của Javascript mà không dùng các hàm xử lý vòng lặp for, forEach…vv khác. Mình sẽ giải thích luôn mục đích là để tối ưu vòng lặp.
  Bài toán của mình ở đây chỉ cần một khoảng trong nhiều khoảng bị overlap là sẽ trả về kết quả luôn không chạy vòng lặp tiếp nữa, nói dễ hiểu hơn: nếu mình kiểm tra một khoảng thời gian với 10 khoảng khác, giả sử tới khoảng thứ 5 thì bị overlap, lúc này thằng Array.some sẽ dừng vòng lặp luôn và trả về kết quả cho mình, không chạy tiếp 5 vòng tiếp theo nữa.
  (Đây là những kinh nghiệm tối ưu vòng lặp, tối ưu code mà sau này đi làm các bạn sẽ gặp rất nhiều đấy nhé ^^)

Tiếp theo thì đơn giản là mình tạo ra 4 khoảng thời gian mẫu để test thử thôi, không có gì khó hiểu cả, chỉ có một lưu ý nhỏ là khoảng thời gian mình để chuỗi string date cho các bạn dễ đọc, còn lúc truyền vào hàm để check thì cần convert chúng về dạng timestamp (kiểu dữ liệu number) để so sánh, mình có dùng hàm getTime() của javascript.

Và để test thử thì chỉ cần chạy lệnh sau để thực thi file main.js: node main.js, kết quả chúng ta thu được sẽ là:

Các bạn cũng có thể dễ dàng thay đổi thời gian tuỳ ý và chạy lại để kiểm tra kết quả thoải mái nhé.

---

3. Full source code trên Github

Vậy là kết thúc bài hôm nay chúng ta đã cùng nhau hoàn thiện về ý tưởng và cách triển khai cho thuật toán kiểm tra nhiều khoảng thời gian có bị trùng lặp, chồng chéo (overlap) rồi.

Mình có để full source code của bài hôm nay ở repo này cho các bạn tham khảo nhé, nếu thấy bài viết bổ ích, hãy ủng hộ bằng cách cho mình 1 star trên repo này để mình có động lực tiếp tục viết những bài viết chất lượng nha, cảm ơn các bạn.
https://github.com/trungquandev/js-check-datetime-ranges-overlap

---

Cảm ơn các bạn đã dành thời gian đọc bài viết.

Xin chào và hẹn gặp lại các bạn ở những bài viết tiếp theo.

Best Regards – Trung Quân – Green Cat

---

Tham khảo kiến thức:

https://stackoverflow.com/questions/325933/determine-whether-two-date-ranges-overlap

“Thanks for awesome knowledges.”