Bài toán Tìm thời điểm gặp gỡ nhiều bạn nhất tại câu lạc bộ tin học

NỘI DUNG

Bài toán

Một nhóm gồm n bạn học sinh của một lớp tham gia một câu lạc bộ tin học vào dịp nghỉ hè. Biết rằng khoảng thời gian mà bạn thứ i có mặt tại câu lạc bộ là [ai, bi] (ai<bi tương ứng là các thời điểm đến và rời khỏi câu lạc bộ). Cô giáo chủ nhiệm lớp muốn tới thăm các bạn trong nhóm này. Hãy giúp cô giáo chủ nhiệm xác định thời điểm đến câu lạc bộ sao cho tại thời điểm đó cô giáo có thể gặp được nhiều bạn trong nhóm nhất.

Dữ liệu: Vào từ file văn bản MEETING.INP:

– Dòng đầu tiên ghi số nguyên dương n (n <= 1000);

– Dòng thứ i trong số n dòng tiếp theo ghi 2 số nguyên không âm ai, bi , i = 1, 2, …, n.

Kết quả: Ghi ra file văn bản MEETING.OUT:

– Dòng đầu tiên ghi số nguyên dương k là số lượng bạn đang có mặt ở câu lạc bộ tại thời điểm cô giáo đến;

– Trong k dòng tiếp theo ghi chỉ số của k bạn có mặt ở câu lạc bộ tại thời điểm cô giáo đến, mỗi dòng ghi một chỉ số của một bạn.

Ví dụ:

MEETING.INP

MEETING.OUT

MEETING.INP

MEETING.OUT

1 2

2 3

2 5

5 7

6 7

9 11

1 2

3 5

7 9

11 15

17 21

Thuật toán

Để giải quyết bài toán này, ta có thể sử dụng thuật toán Greedy để tìm ra thời điểm đến câu lạc bộ sao cho có thể gặp được nhiều bạn nhất.

Bước 1: Đọc dữ liệu từ file MEETING.INP, lưu trữ vào một mảng các cặp giá trị (ai, bi) thể hiện thời gian có mặt của các bạn trong câu lạc bộ.

Bước 2: Sắp xếp mảng các cặp giá trị theo thứ tự tăng dần của thời gian bi.

Bước 3: Khởi tạo một mảng đánh dấu visited với n phần tử và ban đầu tất cả các phần tử đều bằng 0.

Bước 4: Duyệt qua mảng các cặp giá trị, với mỗi cặp giá trị (ai, bi), duyệt qua các phần tử từ ai đến bi của mảng visited và đánh dấu chúng bằng 1.

Bước 5: Duyệt lại mảng visited và đếm số phần tử bằng 1, đây sẽ là số lượng bạn có mặt trong câu lạc bộ tại thời điểm cô giáo đến.

Bước 6: Duyệt lại mảng visited và ghi ra các chỉ số của các phần tử bằng 1, đây sẽ là các bạn có mặt trong câu lạc bộ tại thời điểm cô giáo đến.

Bước 7: Ghi kết quả vào file MEETING.OUT.

Độ phức tạp của thuật toán là O(n log n), do sắp xếp mảng các cặp giá trị. Tuy nhiên, với n có giá trị tối đa là 1000, thuật toán sẽ chạy nhanh và không gây ra vấn đề về hiệu suất.

Cài đặt bài toán với Python

with open('MEETING.INP', 'r') as infile, open('MEETING.OUT', 'w') as outfile:
    n = int(infile.readline())
    intervals = []
    for i in range(n):
        a, b = map(int, infile.readline().split())
        intervals.append((a, b))
    intervals.sort(key=lambda x: x[1])
    visited = [0] * n
    for interval in intervals:
        for i in range(interval[0], interval[1] + 1):
            visited[i] = 1
    count = sum(visited)
    outfile.write(str(count) + '\n')
    for i in range(n):
        if visited[i]:
            outfile.write(str(i+1) + '\n')

Ở đây, ta đọc dữ liệu từ file MEETING.INP bằng cách mở file đó với mode r (read) và sử dụng hàm readline() để đọc từng dòng dữ liệu. Sau đó, ta sử dụng hàm split() để tách các giá trị trong mỗi dòng ra thành một list các string, và sử dụng hàm map() để chuyển các giá trị đó sang kiểu integer. Ta lưu trữ các cặp giá trị (ai, bi) vào một danh sách intervals.

Tiếp theo, ta sắp xếp danh sách intervals theo thứ tự tăng dần của giá trị bi bằng cách sử dụng phương thức sort() kèm theo một hàm lambda.

Sau đó, ta khởi tạo một danh sách visited với giá trị ban đầu là 0. Ta duyệt qua mỗi cặp giá trị trong danh sách intervals, và đánh dấu các phần tử tương ứng trong danh sách visited bằng 1.

Cuối cùng, ta đếm số phần tử bằng 1 trong danh sách visited, đó sẽ là số lượng bạn có mặt trong câu lạc bộ tại thời điểm cô giáo đến. Sau đó, ta duyệt lại danh sách visited và ghi ra các chỉ số của các phần tử bằng 1, đó sẽ là các bạn có mặt trong câu lạc bộ tại thời điểm cô giáo đến. Ta ghi kết quả vào file MEETING.OUT bằng cách mở file đó với mode w (write) và sử dụng phương thức write() để ghi kết quả.

Cài đặt bài toán với C++

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    // Đọc dữ liệu từ file MEETING.INP
    ifstream infile("MEETING.INP");
    int n;
    infile >> n;
    vector<pair<int, int>> intervals(n);
    for (int i = 0; i < n; i++) {
        infile >> intervals[i].first >> intervals[i].second;
    }

    // Sắp xếp các khoảng thời gian theo thời điểm kết thúc
    sort(intervals.begin(), intervals.end(), [](pair<int, int> a, pair<int, int> b) {
        return a.second < b.second;
    });

    // Tìm các khoảng thời gian trùng nhau và lưu vào một vector
    vector<int> overlapping_intervals;
    int latest_end_time = -1;
    for (int i = 0; i < n; i++) {
        if (intervals[i].first <= latest_end_time) {
            overlapping_intervals.push_back(i);
        }
        latest_end_time = max(latest_end_time, intervals[i].second);
    }

    // Xuất kết quả ra file MEETING.OUT
    ofstream outfile("MEETING.OUT");
    outfile << overlapping_intervals.size() << endl;
    for (int i : overlapping_intervals) {
        outfile << i + 1 << endl;
    }

    return 0;
}

Trong cài đặt này, ta đọc dữ liệu từ file MEETING.INP vào một vector intervals chứa các khoảng thời gian của các bạn học sinh. Sau đó, ta sắp xếp các khoảng thời gian theo thời điểm kết thúc (tức là b), và tìm các khoảng thời gian trùng nhau bằng cách duyệt qua từng khoảng thời gian và so sánh với thời điểm kết thúc của khoảng thời gian trước đó. Nếu khoảng thời gian hiện tại bắt đầu trước khi khoảng thời gian trước đó kết thúc, thì ta coi hai khoảng thời gian đó trùng nhau.

Sau khi tìm được các khoảng thời gian trùng nhau, ta xuất kết quả ra file MEETING.OUT. Ở đây, ta lưu chỉ số của các khoảng thời gian trong vector intervals, và để xuất ra file, ta cộng thêm một đơn vị để chuyển từ chỉ số bắt đầu từ 0 sang chỉ số bắt đầu từ 1.

Các cách cài đặt khác

Bài toán tìm thời điểm tối ưu để gặp nhiều học sinh nhất có thể được giải bằng nhiều phương pháp khác nhau, ví dụ:

Brute-force: Đây là phương pháp tìm kiếm tất cả các khả năng có thể có của thời điểm gặp học sinh. Đầu tiên, ta sẽ liệt kê tất cả các khung giờ có thể có, rồi với mỗi khung giờ đó, ta sẽ đếm số lượng học sinh có mặt trong đó. Cuối cùng, ta sẽ tìm ra khung giờ có số lượng học sinh lớn nhất. Tuy nhiên, phương pháp này chỉ thích hợp với bài toán có số lượng học sinh nhỏ, vì độ phức tạp thời gian của nó là O(n^3).

Sử dụng Heap: Một cách tiếp cận khác là sử dụng một Heap (hàng đợi ưu tiên) để lưu trữ các sự kiện, với mỗi sự kiện là thời điểm một học sinh đến hoặc rời đi câu lạc bộ. Khi duyệt qua từng sự kiện trong Heap, ta sẽ cập nhật số lượng học sinh đang có mặt trong câu lạc bộ và tìm ra thời điểm tối ưu để gặp học sinh. Độ phức tạp thời gian của thuật toán này là O(nlogn), với n là số lượng học sinh.

Sắp xếp và đếm: Phương pháp này sắp xếp tất cả các thời điểm đến và rời của học sinh theo thứ tự tăng dần. Sau đó, ta duyệt qua các thời điểm này và đếm số lượng học sinh đang có mặt trong câu lạc bộ tại mỗi thời điểm, và lưu trữ thời điểm tối ưu để gặp học sinh. Độ phức tạp thời gian của thuật toán này là O(nlogn), với n là số lượng học sinh.

Thuật toán tìm kiếm nhị phân: để tìm khoảng thời gian chung lớn nhất giữa các học sinh. Độ phức tạp của thuật toán này là O(nlogn) do việc sắp xếp lại các thời điểm đến và đi theo thứ tự tăng dần có độ phức tạp là O(nlogn) và sau đó áp dụng giải thuật tìm kiếm nhị phân có độ phức tạp O(logn) để tìm khoảng thời gian chung.

Các phương pháp trên đều có ưu điểm và hạn chế của mình. Việc lựa chọn phương pháp tối ưu sẽ phụ thuộc vào số lượng học sinh và độ lớn của dữ liệu đầu vào. Để so sánh thì thuật toán tìm kiếm nhị phân có độ phức tạp tốt hơn. Thuật toán tìm kiếm nhị phân cũng rất hiệu quả trong thực tế, vì nó có độ phức tạp tối ưu và cũng không yêu cầu một lượng bộ nhớ lớn như thuật toán đầu tiên.

Tuy nhiên, nếu số lượng học sinh là nhỏ thì sử dụng thuật toán Brute Force cũng không gây ra vấn đề về độ phức tạp. Do đó, khi giải quyết bài toán tìm thời điểm gặp nhau của các học sinh, ta cần cân nhắc và chọn thuật toán phù hợp với kích thước của dữ liệu đầu vào để đảm bảo tính hiệu quả của giải pháp.

Dưới đây là cài đặt của của thuật toán tìm kiếm nhị phân cho bài toán trên. Các phương pháp còn lại các bạn có thể tự tìm hiểu nhé.

Cài đặt thuật toán tìm kiếm nhị phân với Python

n = int(input())
times = []
for i in range(n):
    a, b = map(int, input().split())
    times.append((a, b))

times.sort()

def can_meet(mid):
    cnt = 0
    for i in range(n):
        if mid >= times[i][0] and mid <= times[i][1]:
            cnt += 1
    return cnt

left = times[0][0]
right = times[n-1][1]
ans = -1

while left <= right:
    mid = (left + right) // 2
    if can_meet(mid) >= 2:
        ans = mid
        left = mid + 1
    else:
        right = mid - 1

if ans == -1:
    print("Khong co thoi diem nao thoa man")
else:
    cnt = 0
    result = []
    for i in range(n):
        if ans >= times[i][0] and ans <= times[i][1]:
            cnt += 1
            result.append(i+1)
    print(cnt)
    for r in result:
        print(r)

Cài đặt thuật toán tìm kiếm nhị phân với C++

#include <bits/stdc++.h>
using namespace std;

int binarySearch(int arr[], int n, int x, int y) {
    int l = 0, r = n-1, mid;
    while (l <= r) {
        mid = (l + r) / 2;
        if (arr[mid] >= x && arr[mid] <= y)
            return mid+1;
        else if (arr[mid] < x)
            l = mid+1;
        else
            r = mid-1;
    }
    return 0;
}

int main() {
    int n;
    cin >> n;
    int a[n], b[n];
    for (int i = 0; i < n; i++)
        cin >> a[i] >> b[i];

    // Sắp xếp các khoảng thời gian theo thời điểm bắt đầu
    sort(a, a+n);

    // Tìm khoảng thời gian có số lượng bạn có mặt tối đa
    int max_cnt = 0, max_start = -1;
    for (int i = 0; i < n; i++) {
        int cnt = binarySearch(a, n, a[i], b[i]) - i;
        if (cnt > max_cnt) {
            max_cnt = cnt;
            max_start = a[i];
        }
    }

    // In kết quả
    cout << max_cnt << endl;
    for (int i = 0; i < n; i++) {
        if (a[i] <= max_start && b[i] >= max_start)
            cout << i+1 << endl;
    }

    return 0
}

Lập trình C/C++, Lập trình Python