#include <string>
#include <vector>
#include<iostream>
#include<algorithm>
using namespace std;
struct Bus {
int curPop, hour, mint; //버스 현재 인원, 출발 시, 출발 분
};
vector<Bus> bus;
string solution(int n, int t, int m, vector<string> timetable) {
string answer = "";
int hour = 9, minute = 0;
for (int i = 0; i < n; i++) {
bus.push_back({ 0, hour, minute });
minute += t;
if (minute >= 60) {
hour++;
minute -= 60;
}
}
sort(timetable.begin(), timetable.end());
//일찍 온 사람부터 나오게 정렬(마지막에 탄사람이 제일 늦게 온 사람인데, 그 사람 찾으려고)
int lastUp = 0; // 마지막에 탄 사람의 인덱스
for (int i = 0; i < timetable.size(); i++) {
int hr = stoi(timetable[i].substr(0, 2));
int mn = stoi(timetable[i].substr(3, 2));
for (int j = 0; j < bus.size(); j++) {
if (bus[j].curPop < m && (bus[j].hour > hr || (bus[j].hour == hr && bus[j].mint >= mn))) {
bus[j].curPop++;
lastUp = i;
break; //탈 버스가 정해졌으면 버스 검색 중지
}
}
}
string hrStr = "";
string mnStr = "";
if (bus[bus.size() - 1].curPop < m) { //막차에 자리가 남았다면 막차 시간에 오면 됨
hrStr = to_string(bus[bus.size() - 1].hour);
mnStr = to_string(bus[bus.size() - 1].mint);
}
else { //막차에 자리가 없으면, 마지막에 탄 사람보다 1분 일찍오면 무조건 탈 수 있음
int lastHr = stoi(timetable[lastUp].substr(0, 2));
int lastMin = stoi(timetable[lastUp].substr(3, 2));
lastMin--;
if (lastMin < 0) {
lastHr--;
lastMin += 60;
}
hrStr = to_string(lastHr);
mnStr = to_string(lastMin);
}
if (hrStr.length() == 1) hrStr = '0' + hrStr;
if (mnStr.length() == 1) mnStr = '0' + mnStr;
answer = hrStr + ':' + mnStr;
return answer;
}