UVa 419 Matching Meetings

题目描述题目要求为nnn次会议安排时间。给定当前日期、每次会议的持续时间ttt以151515分钟为单位以及最多100100100个人的日程安排。每个人有若干预约每个预约包含日期、开始时间和结束时间时间范围为09:0009:0009:00到17:0017:0017:00。需要找出nnn个最早的会议时间使得所有人在该时间段内都空闲。会议时间不能与任何人的已有预约冲突且一旦某个时间被安排用于一次会议该时间即被占用不能用于后续会议。如果可用的会议时间少于nnn个则输出所有可用时间并输出No more times available。输入格式第一行当前日期格式为dayname month date其中dayname为单个字符M表示周一T表示周二W表示周三R$表示周四F表示周五month和date为整数。第二行两个整数nnn和tttnnn表示需要安排的会议数量ttt表示每次会议的持续时间以分钟为单位是151515的倍数。接下来若干行每个人的日程。每个人以一行名字开始之后若干行表示该人的预约每行格式为dayname month date start_time end_time时间格式为444位数字如090009000900表示09:0009:0009:00。每人日程以一行done结束。输入以一行done结束。输出格式输出nnn行每行一个会议时间格式为dayname month date start_time其中start_time为444位数字。会议按日期和时间升序排列。如果可用时间少于nnn个则输出所有可用时间后再输出一行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题目分析本题的核心是在给定多人的日程安排中找出所有人都空闲的连续时间段并从中选出最早的nnn个每次选完后将该时间段标记为已占用。时间表示工作时间范围为09:0009:0009:00到17:0017:0017:00共888小时即480480480分钟。由于会议时间以151515分钟为增量可以将每天的工作时间划分为480/1532480 / 15 32480/1532个时段每个时段对应151515分钟。时段索引000对应09:00−09:1509:00-09:1509:00−09:15时段313131对应16:45−17:0016:45-17:0016:45−17:00。日期范围输入给出了当前日期且预约不会早于当前日期也不会超过当前日期之后一年。由于忽略闰年一年按365365365天计算。需要遍历从当前日期开始的一年内所有工作日周一到周五因为周末不安排会议。日程表示对于每个日期用一个长度为323232的布尔数组或bitset\texttt{bitset}bitset表示该日期每个时段是否被某人的预约占用。初始全为false\texttt{false}false空闲。读取每个人的预约时将预约覆盖的时段标记为true\texttt{true}true忙碌。由于多个人的预约需要合并最终某个时段的忙碌状态是所有人的预约在该时段的“或”结果。寻找可用会议时间对于每个工作日按日期升序扫描当天的323232个时段寻找连续requiredSlotst/15\textit{requiredSlots} t / 15requiredSlotst/15个空闲时段。一旦找到这样的连续时段即得到一个可用的会议时间起始时间即为该时段对应的时刻。将该会议占用的所有时段标记为忙碌以便后续会议不会重复使用同一时间然后继续寻找下一个会议。如果已找到nnn个会议则停止。输出按找到的顺序输出会议时间由于按日期升序、同一天内按时段升序扫描输出自然有序。如果找到的会议数少于nnn则输出所有找到的会议后再输出No more times available。复杂度分析最多考虑365365365天每天323232个时段每次检查连续空闲时段需要O(requiredSlots)O(\textit{requiredSlots})O(requiredSlots)时间总复杂度O(365×32×requiredSlots)O(365 \times 32 \times \textit{requiredSlots})O(365×32×requiredSlots)requiredSlots≤32\textit{requiredSlots} \le 32requiredSlots≤32完全可接受。代码实现// Matching Meetings// UVa ID: 419// Verdict: Accepted// Submission Date: 2025-12-03// UVa Run Time: 0.000s//// 版权所有C2025邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;// 星期字符映射mapchar,intdayIndex{{M,0},{T,1},{W,2},{R,3},{F,4},{A,5},{S,6}};string dayStrMTWRF;structDate{// 星期几从 0 开始计数0 对应星期一6 对应星期日// 月份从 0 开始计数0 对应 1 月11 对应 12 月份// 天数从 1 开始计数intdayIdx;intmonth;intday;booloperator(constDateother)const{if(month!other.month)returnmonthother.month;returndayother.day;}booloperator(constDateother)const{returnmonthother.monthdayother.day;}};// 时间转换为分钟数inttimeToMinutes(inthour,intminute){returnhour*60minute;}// 日期增加天数DateaddDays(constDatedate,intdays){Date resultdate;result.daydays;intdaysInMonth[]{31,28,31,30,31,30,31,31,30,31,30,31};while(result.daydaysInMonth[result.month]){result.day-daysInMonth[result.month];result.month;// 调整月份result.month%12;}result.dayIdx(result.dayIdxdays)%7;returnresult;}intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);// 读取当前日期chardayChar;intcurMonth,curDay;cindayCharcurMonthcurDay;Date currentDate{dayIndex[dayChar],curMonth-1,curDay};intn,t;cinnt;// 一天从9:00到17:00共8小时每15分钟一个时段共32个时段constintSLOTS_PER_DAY32;constintSTART_HOUR9;// 存储所有可能的日期从当前日期开始一年内vectorDateallDates;Date curDatecurrentDate;for(inti0;i365;i){// 忽略休息日if(curDate.dayIdx5)allDates.push_back(curDate);curDateaddDays(curDate,1);}// 为每个日期创建一个bitset初始全0表示都空闲mappairint,int,bitsetSLOTS_PER_DAYdateBusy;// 忽略换行符cin.ignore(128,\n);// 读取每个人的日程string name;while(getline(cin,name)){if(namedone)break;// 读取这个人的预约string line;while(getline(cin,line)){if(linedone)break;istringstreamiss(line);chardayChar;intmonth,day;string startStr,endStr;issdayCharmonthdaystartStrendStr;// 解析时间intstartHourstoi(startStr.substr(0,2));intstartMinstoi(startStr.substr(2,2));intendHourstoi(endStr.substr(0,2));intendMinstoi(endStr.substr(2,2));// 转换为时段索引intstartSlot(startHour-START_HOUR)*4startMin/15;intendSlot(endHour-START_HOUR)*4endMin/15;// 确保在有效范围内startSlotmax(0,startSlot);endSlotmin(SLOTS_PER_DAY,endSlot);// 标记忙碌时段autodateKeymake_pair(month-1,day);for(intslotstartSlot;slotendSlot;slot)dateBusy[dateKey].set(slot);}}// 寻找可用的会议时间vectorpairDate,pairint,intmeetings;// 日期小时分钟// 需要占用的时段数intrequiredSlotst/15;// 检查每个日期for(constDatedate:allDates){autodateKeymake_pair(date.month,date.day);bitsetSLOTS_PER_DAYbusydateBusy[dateKey];// 寻找连续requiredSlots个空闲时段for(intstartSlot0;startSlotSLOTS_PER_DAY-requiredSlots;startSlot){boolavailabletrue;for(inti0;irequiredSlots;i){if(busy[startSloti]){availablefalse;break;}}if(available){// 找到可用时段计算开始时间inttotalMinutesstartSlot*15;inthourSTART_HOURtotalMinutes/60;intminutetotalMinutes%60;meetings.push_back({date,{hour,minute}});// 标记这些时段为已占用给后续会议for(inti0;irequiredSlots;i)busy.set(startSloti);// 如果已经找到足够多的会议可以提前停止if(meetings.size()n)break;}}if(meetings.size()n)break;}// 输出结果intoutputCountmin(n,(int)meetings.size());for(inti0;ioutputCount;i){constDatedatemeetings[i].first;inthourmeetings[i].second.first;intminutemeetings[i].second.second;printf(%c %d %d %02d%02d\n,dayStr[date.dayIdx],date.month1,date.day,hour,minute);}if(outputCountn)coutNo more times available\n;return0;}