[백준 7507] 올림픽 게임 (C++)

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

7507번: 올림픽 게임

문제

---

상근이는 올림픽을 매우 좋아하면서 싫어한다. 올림픽을 좋아하는 이유는 많은 스포츠 경기를 볼 수 있기 때문이고, 싫어하는 이유는 경기가 동시에 열리기 때문이다.

방금 올림픽이 열리는 장소에 도착을 했다. 하지만, 경기가 동시에 열리기 때문에, 상근이는 모든 경기를 실시간으로 볼 수 없다.

모든 경기의 시작 시간과 종료 시간, 그리고 날짜가 주어진다. 이때, 상근이가 볼 수 있는 경기의 최대 개수를 구하는 프로그램을 작성하시오. 상근이는 경기장에 시작 시간에 들어가며, 종료 시간에 나오게된다. 한 경기를 보던 중에 다른 경기를 보기 위해 경기장을 옮길 수 없다. 또, 경기장을 이동하는데 걸리는 시간은 없다. 마지막으로, 경기가 시작된 이후에는 경기장에 들어갈 수 없다.

 

입력

---

입력의 첫째 줄에는 테스트 케이스의 개수 n이 주어진다.

각 테스트 케이스의 첫째 줄에는 경기의 수  1 ≤ m ≤ 50000 이 주어진다. 다음 m개 줄에는 각 경기의 정보를 나타내는 세 정수 d, s, e가 주어진다. d는 경기의 날짜, s는 시작 시간, e는 종료 시간을 나타낸다. 시간은 hhmm형식으로 주어지며, 모든 경기는 시작한 날에 끝난다.

 

출력

---

각 테스트 케이스마다 "Scenario #i:"를 출력한다. 여기서 i는 테스트 케이스 번호이며 1부터 시작한다. 그 다음 줄에는 상근이가 참석할 수 있는 경기의 최대 개수를 출력한다. 문제에서도 설명했지만, 경기장을 이동하는데 걸리는 시간은 없다. 즉, 경기 A의 종료 시간이 B의 시작 시간과 같은 경우에 상근이는 A 이후에 바로 B로 이동할 수 있다. 각 테스트 케이스 사이에는 빈 줄을 하나 출력한다.

 

문제 풀이

---

정렬과 그리디를 사용하는 문제.

1931 회의실 배정과 문제 풀이가 같다.

종료 시간이 빠른 순으로 정렬하여 이전에 관람한 경기의 종료시간보다 현재 관람여부를 확인할 경기의 시작시간이 더 나중에 위치한다면 해당 경기를 관람한다. 그리고 관람한 경기를 해당 경기로 바꾼다.

 

아래는 코드.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct info
{
	int day;
	string start;
	string end;
	info(int a, string b, string c)
	{
		day = a;
		start = b;
		end = c;
	}
};

bool cmp(info& i1, info& i2)
{
	if (i1.day < i2.day)
	{
		return true;
	}
	else if (i1.day == i2.day)
	{
		if (i1.end < i2.end)
		{
			return true;
		}
		else if (i1.end == i2.end)
		{
			return i1.start < i2.start;
		}
		else
		{
			return false;
		}
	}
	else
	{
		return false;
	}
}

int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);
	int T, N;
	int day;
	string start, end;
	cin >> T;
	for (int t = 0; t < T; t++)
	{
		cin >> N;
		vector<info> v;
		int answer = 1;
		for (int i = 0; i < N; i++)
		{
			cin >> day >> start >> end;
			v.push_back(info(day, start, end));
		}
		sort(v.begin(), v.end(), cmp);
		info prev = v.at(0);
		for (int i = 1; i < N; i++)
		{
			if (v.at(i).day == prev.day && v.at(i).start >= prev.end)
			{
				prev = v.at(i);
				answer++;
			}
			else if (v.at(i).day != prev.day)
			{
				answer++;
				prev = v.at(i);
			}
		}
		cout <<"Scenario #"<<t+1<<":" << "\n" << answer << "\n";
		if (t != T - 1)
		{
			cout << "\n";
		}
	}
	return 0;
}