[BOJ/Gold 5] 백준 22867 종점(C++)

문제 링크

https://www.acmicpc.net/problem/22867

22867번: 종점

 

문제

주행을 마친 버스들이 종점에 들어온다. 종점에 들어온 버스는 버스를 정비하기 위한 자리에 들어간다. 즉, 종점에 버스 4대가 있다면 버스를 정비할 수 있는 공간이 최소 4개 이상 필요하다. 만약 같은 시각에 종점에 들어오는 버스 A와 종점에서 출발하는 버스 B가 있을 경우는 버스 B가 먼저 종점에서 출발하고 그 다음으로 버스 A가 종점으로 들어온다.

버스의 시간표가 매일 동일하며 종점에 들어오는 시각과 나가는 시각이 매일 동일하다.

이번에 버스 시간표가 변경이 되어 버스를 정비하는 공간이 최소 몇 개 이상 필요한지 다시 계산을 해야한다. 이를 도와 계산을 해주자.

입력

첫 번째 줄에는 종점에 들어오는 버스들의 개수 N이 주어진다.

두 번째 줄부터 N+1번째 줄까지 각 버스가 종점에 들어오는 시각과 종점에서 나가는 시각이 주어진다.

주어지는 시각의 형식은 다음과 같다. HH:MM:SS.sss (HH는 시각을, MM은 분, SS은 초, sss 밀리초를 의미한다.)

출력

버스 정비를 위한 공간이 최소 몇 개 이상 필요한지 출력한다.

제한

•  1≤N≤100,000
•  0≤HH<24
•  0≤MM<60
•  0≤SS<60
•  0≤sss<1000

예제 입력 1

4
06:00:00.000 06:30:00.000
06:10:45.000 06:15:00.000
06:30:00.000 06:40:00.000
06:01:00.001 06:40:00.001

예제 출력 1

3

알고리즘 분류

• 문자열
• 자료 구조

풀이

정비 공간 우선순위 큐(STATION)를 선언해 나가는 시각을 기준으로 오름차순한다. 나가는 시각이 같으면 들어오는 시각을 기준으로 내림차순한다.

현재 버스의 들어오는 시각이 STATION의 top의 나가는 시각보다 크다면 STATION에 있는 버스들 중 현재 버스의 들어오는 시각보다 해당 버스의 나가는 시각이 더 작다면 pop해준다. 즉 정비 시간이 겹치지 않는 버스들을 빼준다.

코드

#include <iostream>
#include <string>
#include <cmath>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#include <climits>
#define FASTIO cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define MAX 100001
#define LL long long
#define INF 1e9

using namespace std;
struct COMP {
	bool operator() (pair<int, int> A, pair<int, int> B) {
		if (A.first == B.first) {
			return (A.second > B.second);
		}
		return (A.first > B.first);
	}
};

struct COMP2 {
	bool operator() (pair<int, int> A, pair<int, int> B) {
		if (A.second == B.second) {
			return (A.first < B.first);
		}
		return (A.second > B.second);
	}
};

int N;
string InTime, OutTime;
priority_queue<pair<int, int>, vector<pair<int, int> >, COMP> BUS;
priority_queue<pair<int, int>, vector<pair<int, int> >, COMP2> STATION;
int Cnt = 0;
int answer = 0;

int TimeCalc(string S) {
	string Hour = S.substr(0, 2);
	string Minute = S.substr(3, 2);
	string Sec = S.substr(6, 2);
	string mSec = S.substr(9, 3);
	return ((stoi(Hour) * 3600000) + (stoi(Minute) * 60000) + (stoi(Sec) * 1000) + stoi(mSec));
}

void Input() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> InTime >> OutTime;
		BUS.push(make_pair(TimeCalc(InTime), TimeCalc(OutTime)));
	}
}

void Settings() {
	STATION.push(BUS.top());
	BUS.pop();
	answer++;
	Cnt++;
	while (!BUS.empty()) {
		int In = BUS.top().first;
		int Out = BUS.top().second;
		if (STATION.top().second <= In) {
			while (!STATION.empty()) {
				int Out2 = STATION.top().second;
				if (Out2 <= In) {
					STATION.pop();
					Cnt--;
				}
				else {
					break;
				}
			};
		}
		STATION.push(BUS.top());
		BUS.pop();
		Cnt++;
		answer = max(answer, Cnt);
	};
}

void Find_Answer() {
	cout << answer << "\n";
}

int main() {
	FASTIO
	Input();
	Settings();
	Find_Answer();

	return 0;
}