题目描述

给定当前日期、需要安排的会议数量 n（n 为整数），以及每次会议的持续时间 t（t 为分钟数，且为 15 的倍数）。随后提供最多 100 个人的日程安排，每个人的日程包含若干预约，每个预约指定了日期、开始时间和结束时间（时间范围为 09:00 至 17:00）。需要找出 n 个最早的会议时间，使得所有人在该时间段内均处于空闲状态。会议时间不能与任何人的已有预约冲突，一旦某个时间被安排用于一次会议，该时间即被占用，不能用于后续会议。如果可用的会议时间少于 n 个，则输出所有可用时间，并输出一行 "No more times available"。

输入格式

第一行：当前日期，格式为 "dayname month date"，其中 dayname 为单个字符（M 表示周一，T 表示周二，W 表示周三，R 表示周四，F 表示周五），month 和 date 为整数。

第二行：两个整数 n 和 t，n 表示需要安排的会议数量，t 表示每次会议的持续时间（以分钟为单位，且为 15 的倍数）。

接下来若干行：每个人的日程。每个人以一行名字开始，之后若干行表示该人的预约，每行格式为 "dayname month date start_time end_time"，时间格式为 4 位数字（如 0900 表示 09:00）。每人的日程以一行 "done" 结束。

输入以一行 "done" 结束。

输出格式

输出 n 行，每行一个会议时间，格式为 "dayname month date start_time"，其中 start_time 为 4 位数字。会议按日期和时间升序排列。如果可用时间少于 n 个，则输出所有可用时间后，再输出一行 "No more times available"。

样例

输入
M 8 21
2 60
Jack Casey
M 8 21 0900 1015
done
Jack Ross
M 8 21 1000 1100
M 8 21 1200 1700
done
Jack Swigert
M 8 21 1600 1700
T 8 22 0900 1000
done
done

输出
M 8 21 1100
T 8 22 1000

题目分析

本题的核心是在给定多人的日程安排中，找出所有人都空闲的连续时间段，并从中选出最早的 n 个，每次选完后将该时间段标记为已占用。

时间表示

工作时间范围为 09:00 至 17:00，共 8 小时，即 480 分钟。由于会议时间以 15 分钟为增量，可以将每天的工作时间划分为 480 / 15 = 32 个时段，每个时段对应 15 分钟。时段索引 0 对应 09:00-09:15，时段索引 31 对应 16:45-17:00。

日期范围

输入给出了当前日期，且预约不会早于当前日期，也不会超过当前日期之后一年。由于忽略闰年，一年按 365 天计算。需要遍历从当前日期开始的一年内所有工作日（周一到周五），因为周末不安排会议。

日程表示

对于每个日期，用一个长度为 32 的布尔数组（或 bitset）表示该日期每个时段是否被某人的预约占用。初始全为 false（空闲）。读取每个人的预约时，将预约覆盖的时段标记为 true（忙碌）。由于多个人的预约需要合并，最终某个时段的忙碌状态是所有人的预约在该时段的"或"结果。

寻找可用会议时间

对于每个工作日（按日期升序），扫描当天的 32 个时段，寻找连续 requiredSlots = t / 15 个空闲时段。一旦找到这样的连续时段，即得到一个可用的会议时间，起始时间即为该时段对应的时刻。将该会议占用的所有时段标记为忙碌（以便后续会议不会重复使用同一时间），然后继续寻找下一个会议。如果已找到 n 个会议，则停止。

输出

按找到的顺序输出会议时间（由于按日期升序、同一天内按时段升序扫描，输出自然有序）。如果找到的会议数少于 n，则输出所有找到的会议后，再输出一行 "No more times available"。

复杂度分析

最多考虑 365 天，每天 32 个时段，每次检查连续空闲时段需要 O(requiredSlots) 时间，总复杂度 O(365 × 32 × requiredSlots)，其中 requiredSlots ≤ 32，完全可接受。

代码实现

// UVa 419 会议匹配问题
// 包含必要的头文件
#include <bits/stdc++.h>
using namespace std;

// 日期结构体，存储星期索引、月份和日期
struct Date {
    int dayIndex;  // 星期索引，0 对应周一，6 对应周日
    int month;     // 月份，从 0 开始计数（0 表示 1 月）
    int day;       // 日期，从 1 开始计数
    // 重载小于运算符，用于日期比较
    bool operator<(const Date& other) const {
        if (month != other.month) return month < other.month;
        return day < other.day;
    }
    // 重载等于运算符
    bool operator==(const Date& other) const {
        return month == other.month && day == other.day;
    }
};

// 星期字符到索引的映射
map<char, int> dayToIndex = {{'M', 0}, {'T', 1}, {'W', 2}, {'R', 3}, {'F', 4}};
// 索引到星期字符的字符串
string indexToDay = "MTWRF";

// 辅助函数：将小时和分钟转换为总分钟数
int timeToMinutes(int hour, int minute) {
    return hour * 60 + minute;
}

// 辅助函数：增加日期的天数
Date addDays(const Date& date, int days) {
    Date result = date;
    result.day += days;
    // 每个月的天数，假设非闰年
    int daysInMonth[] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
    // 处理日期溢出，调整月份
    while (result.day > daysInMonth[result.month]) {
        result.day -= daysInMonth[result.month];
        result.month++;
        result.month %= 12; // 防止月份超过 11
    }
    // 更新星期索引
    result.dayIndex = (result.dayIndex + days) % 7;
    return result;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    // 读取当前日期
    char dayChar;
    int curMonth, curDay;
    cin >> dayChar >> curMonth >> curDay;
    Date currentDate = {dayToIndex[dayChar], curMonth - 1, curDay};
    
    int n, t;
    cin >> n >> t;
    
    // 常量定义：每天时段数，开始工作小时
    const int SLOTS_PER_DAY = 32;
    const int START_HOUR = 9;
    
    // 生成一年内所有工作日（周一到周五）
    vector<Date> workDays;
    Date curDate = currentDate;
    for (int i = 0; i < 365; i++) {
        if (curDate.dayIndex < 5) { // 只考虑工作日
            workDays.push_back(curDate);
        }
        curDate = addDays(curDate, 1);
    }
    
    // 使用 map 存储每个日期的忙碌时段，键为月份和日期对，值为 bitset
    map<pair<int, int>, bitset<SLOTS_PER_DAY>> busyMap;
    
    // 忽略换行符，准备读取名字
    cin.ignore(128, '\n');
    string name;
    while (getline(cin, name)) {
        if (name == "done") break;
        // 读取该人的预约
        string line;
        while (getline(cin, line)) {
            if (line == "done") break;
            istringstream iss(line);
            char dChar;
            int month, day;
            string startStr, endStr;
            iss >> dChar >> month >> day >> startStr >> endStr;
            // 解析时间字符串
            int startHour = stoi(startStr.substr(0, 2));
            int startMin = stoi(startStr.substr(2, 2));
            int endHour = stoi(endStr.substr(0, 2));
            int endMin = stoi(endStr.substr(2, 2));
            // 计算开始和结束时段索引
            int startSlot = (startHour - START_HOUR) * 4 + startMin / 15;
            int endSlot = (endHour - START_HOUR) * 4 + endMin / 15;
            // 确保时段在有效范围内
            startSlot = max(0, startSlot);
            endSlot = min(SLOTS_PER_DAY, endSlot);
            // 标记该日期的忙碌时段
            auto dateKey = make_pair(month - 1, day);
            for (int slot = startSlot; slot < endSlot; slot++) {
                busyMap[dateKey].set(slot);
            }
        }
    }
    
    // 存储找到的会议：日期和时间（小时、分钟）
    vector<pair<Date, pair<int, int>>> meetings;
    int requiredSlots = t / 15; // 每次会议需要的时段数
    
    // 遍历每个工作日，寻找可用会议时间
    for (const Date& date : workDays) {
        auto dateKey = make_pair(date.month, date.day);
        bitset<SLOTS_PER_DAY> busy = busyMap[dateKey]; // 获取该日期的忙碌状态
        // 滑动窗口检查连续空闲时段
        for (int startSlot = 0; startSlot <= SLOTS_PER_DAY - requiredSlots; startSlot++) {
            bool available = true;
            for (int i = 0; i < requiredSlots; i++) {
                if (busy[startSlot + i]) {
                    available = false;
                    break;
                }
            }
            if (available) {
                // 计算会议开始时间
                int totalMinutes = startSlot * 15;
                int hour = START_HOUR + totalMinutes / 60;
                int minute = totalMinutes % 60;
                meetings.push_back({date, {hour, minute}});
                // 标记这些时段为已占用
                for (int i = 0; i < requiredSlots; i++) {
                    busy.set(startSlot + i);
                }
                // 如果已找到足够会议，提前结束
                if (meetings.size() >= n) break;
            }
        }
        if (meetings.size() >= n) break;
    }
    
    // 输出结果
    int outputCount = min(n, (int)meetings.size());
    for (int i = 0; i < outputCount; i++) {
        const Date& date = meetings[i].first;
        int hour = meetings[i].second.first;
        int minute = meetings[i].second.second;
        printf("%c %d %d %02d%02d\n", indexToDay[date.dayIndex], date.month + 1, date.day, hour, minute);
    }
    if (outputCount < n) {
        cout << "No more times available\n";
    }
    return 0;
}