KIỂM TRA 2 KHOẢNG TRÙNG NHAU TRÊN MỘT TẬP HỢP

Hai khoảng trùng nhau trên một tập hợp là vấn đề khá phổ biến đối với dữ liệu đầu vào của phần mềm, hệ thống.

Ví dụ với các hệ thống booking trong website như việc đặt bàn nhà hàng, đặt phòng khách sạn, đặt lịch hẹn spa hay các trung tâm bảo dưỡng xe hơi thì admin của hệ thống cần đảm bảo rằng không có 2 khách hàng hẹn giờ trùng nhau, trùng phòng ở hay trùng chuyên viên chăm sóc.

Qua bài viết này, tác giả đến từ CO-WELL Asia sẽ chia sẻ cách kiểm tra hai khoảng trùng nhau trên một tập hợp của dữ liệu đầu vào.

Phần 1: Làm quen với “complexity”

Trước khi đi vào tìm ra 2 khoảng trùng nhau, ta sẽ làm quen với khái niệm “độ phức tạp của thuật toán” (complexity). Bởi có rất nhiều cách để tìm ra phần trùng lặp này, tuy nhiên mỗi cách lại có độ phức tạp khác nhau và bạn nên lựa chọn cách nào tối ưu hơn.

• Khái niệm: Để hiểu một cách đơn giản thì mỗi một bài toán có kích thước của đầu vào (inputs), ví dụ như một mảng có n phần tử thì kích thước của mảng là n. Độ phức tạp của thuật toán là một định lượng tương đối thể hiện số phép toán của thuật toán dựa trên kích thước của đầu vào.
• Khi nào cần để ý tới độ phức tạp của thuật toán? Với các dự án nhỏ, thời gian cần hoàn thiện gấp, không yêu cầu về performance (tốc độ xử lý), thì có thể không cần quá quan tâm tới độ phức tạp thuật toán (có thể chỉ cần giải quyết được vấn đề của khách hàng với chất lượng ổn, đúng tiến độ dự án là được).

Còn với các dự án lớn, hoặc dự án yêu cầu khắt khe về performance của sản phẩm, hay với những lập trình viên muốn “luyện tay” viết ra những dòng code chất lượng và những chức năng có mức độ phức tạp thuật toán tối ưu nhất, thì bạn nên để ý hơn tới yếu tố complexity này.

Phần 2: Cách kiểm tra hai khoảng trùng nhau nào đạt độ complexity tối ưu?

Input như sau:

$periods = [

[‘start_time’ => “09:00”, ‘end_time’ => ’10:30′],

[‘start_time’ => “14:30”, “end_time” => “16:30”],

[‘start_time’ => “11:30”, “end_time” => “13:00”],

[‘start_time’ => “10:00”, “end_time” => “11:30”]

];

Nhiệm vụ của công đoạn này là chỉ ra được lỗi của inputs, cụ thể là cặp thời gian ở dòng 1 và dòng 4 đang trùng nhau khoảng thời gian là 10:00 – 10:30.

Hiển nhiên, với các lập trình viên vốn có sự sáng tạo và tư duy logic tốt thì có rất nhiều cách để giải quyết vấn đề này. Một số cách khả thi như sau:

• Cách số 1: Kiểm tra từng cặp [start_time, end_time] trong mảng.

Nếu start_time/ end_time của cặp này nằm giữa start_time/ end_time của cặp kia hay không. Nếu như có thì tức là 2 cặp này bị trùng lặp. Cứ check từng cặp như vậy cho tới khi hết các cặp trong mảng.

Đây là một phương pháp khá tốt với các tập hợp có vài ba phần tử. Tuy nhiên, xét theo độ phức tạp của thuật toán thì phải check từng cặp trong tập hợp. Như vậy khi inputs tăng lên n cặp thời gian thuật toán thì sẽ có độ phức tạp là: tổ hợp chập 2 của n phần tử, tương đương n!/(2! * (n – 2)!) Nghĩa là với n=4 thì cần 6 lần lặp, n=5 thì cần 10 lần lặp, n = xxx con số sẽ rất lớn.

• Cách 2: Sử dụng PHP để triển khai

Coi mỗi một $period là một đoạn thẳng trên đồ thị (theo trục x). Vậy ta có một loạt các đoạn thẳng nằm ngang trên đồ thị, muốn tìm xem nó có trùng lặp hay không thì chỉ cần duyệt theo chiều ngang (trục x).  Ta triển khai bằng PHP như sau:

/**

* Check the two time periods overlap

*

* Example:

* $periods = [

*      [‘start_time’ => “09:00”, ‘end_time’ => ’10:30′],

*      [‘start_time’ => “14:30”, “end_time” => “16:30”],

*      [‘start_time’ => “11:30”, “end_time” => “13:00”],

*      [‘start_time’ => “10:30”, “end_time” => “11:30”],

* ]

*

* @param $periods

* @param string $start_time_key

* @param string $end_time_key

* @return bool

*/

public static function isOverlapped($periods, $start_time_key = ‘start_time’, $end_time_key = ‘end_time’)

{

// order periods by start_time

usort($periods, function ($a, $b) use ($start_time_key, $end_time_key) {

return strtotime($a[$start_time_key]) <=> strtotime($b[$end_time_key]);

});

// check two periods overlap

foreach ($periods as $key => $period) {

if ($key != 0) {

if (strtotime($period[$start_time_key]) < strtotime($periods[$key – 1][$end_time_key])) {

return true;

}

}

}

return false;

}

Giải thích cho phần triển khai trên, đầu tiên cần sắp xếp lại các cặp thời gian trong mảng cho đúng thứ tự start_time. Chú ý là ở đây ta sử dụng một toán tử của PHP 7, gọi là Spaceship. Các bạn có thể tham khảo ở bài viết này.

Tiếp theo ta duyệt mảng $periods đã sắp xếp ở trên theo chiều ngang của đồ thị thôi, lúc nào thấy có bất kỳ 2 đoạn thẳng chồng/đè lên nhau thì trả về kết quả là có sự chồng/đè.

Như vậy, với cách số 2 này, chỉ cần 1 lần duyệt tất cả các cặp trong mảng là có thể tìm ra khoảng trùng lặp.

Tóm lại với bài toán như thế này, có rất nhiều cách để giải quyết ở nhiều mức độ phức tạp khác nhau. Tùy từng bối cảnh cụ thể và cách tư duy mà các lập trình viên hãy lựa chọn các hướng giải quyết cho phù hợp nhé.

XichLo – CO-WELL Asia