# [Gold III] 셔틀버스 [문제 링크](https://www.acmicpc.net/problem/9083) ## 문제 설명 <p>효성이가 다니는 학교에서 멀리서 통학하는 학생들의 편의를 위해서 학교와 터미널 사이를 운행하는 셔틀버스를 도입하기로 하였다. 그리고 셔틀 버스의 운행의 스케줄은 전적으로 학생들의 의견을 따르기로 하였다. 셔틀 버스의 운행 스케줄이 주어질 때 운행에 필요한 버스의 최소의 수를 계산하는 프로그램을 작성하시오. 이때 셔틀 버스를 타고 내리는 시간은 고려하지 않는다.</p> ## 입력 <p>입력의 첫 줄에는 테스트 케이스의 개수 T(1≤ T ≤ 10)가 주어진다. 각 테스트 케이스는 첫 줄에 터미널까지 걸리는 시간 D(1 ≤ D ≤ 120)가 분으로 주어지고, 그 다음 줄에는 학교에서 터미널로 출발하는 시간의 수 A(1 ≤ A ≤ 20)가 주어지고 그 다음에는 A개의 출발 시간이 HH:MM(HH시 MM분)의 형식으로 한 줄에 하나씩 시간 순서대로 주어진다. 그 다음 줄에는 터미널에서 학교로 출발하는 시간의 수 B(1 ≤ B ≤ 20)가 주어지고 그 다음에는 B개의 출발 시간이 HH:MM의 형식으로 한 줄에 하나씩 시간 순서대로 주어진다. 시간은 06:00 ~ 21:00 사이의 값이 주어지며 HH와 MM은 항상 두 자리 숫자로 주어진다(한 자리 숫자일 경우에는 앞에 0을 붙인다.). 같은 출발 장소에서 같은 시각에 출발하는 스케줄이 있을 때에는 각각의 스케줄에 다른 버스가 운행되어야 한다</p> ## 출력 <p>각 테스트 케이스에 대해서 스케줄대로 운행하기 위해 필요한 버스의 최소의 개수를 한 줄에 하나씩 출력한다.</p> ## 풀이 #### 이미 존재하는 버스를 이용하는 경우, #### 1. 같은 지점에 위치한 이용 가능한 버스 중 가장 늦게 도착한 버스 #### 2. 다른 지점에 위치한 이용 가능한 버스 중 가장 늦게 도착한 버스 #### 순서대로 우선순위를 두고 버스를 선택하면 된다. ``` c++ #include<bits/stdc++.h> using namespace std; struct element { int t, type; // 1: A위치, 2: B위치 bool operator<(const element e) const { return t < e.t; } }; int main() { ios::sync_with_stdio(0); cin.tie(0); int t; cin >> t; while(t--) { int d; cin >> d; vector<element> times; int a; cin >> a; while(a--) { int h, m; char ch; cin >> h >> ch >> m; times.push_back({h*60+m, 1}); } int b; cin >> b; while(b--) { int h, m; char ch; cin >> h >> ch >> m; times.push_back({h*60+m, 2}); } sort(times.begin(), times.end()); vector<int> remainA, remainB; for(auto time : times) { if(time.type==1) { if(!remainA.empty() && remainA.front()<=time.t) { int idx=0; for(int i=1;i<remainA.size();i++) { if(remainA[i]<=time.t) idx=i; } remainA.erase(remainA.begin()+idx); } else if(!remainB.empty() && remainB.front()+d<=time.t) { int idx=0; for(int i=1;i<remainB.size();i++) { if(remainB[i]+d<=time.t) idx=i; } remainB.erase(remainB.begin()+idx); } remainB.push_back(time.t+d); } else { if(!remainB.empty() && remainB.front()<=time.t) { int idx=0; for(int i=1;i<remainB.size();i++) { if(remainB[i]<=time.t) idx=i; } remainB.erase(remainB.begin()+idx); } else if(!remainA.empty() && remainA.front()+d<=time.t) { int idx=0; for(int i=1;i<remainA.size();i++) { if(remainA[i]+d<=time.t) idx=i; } remainA.erase(remainA.begin()+idx); } remainA.push_back(time.t+d); } } cout << remainA.size()+remainB.size() << '\n'; } } ```