[백준] C++ 1263번(시간 관리)

최대한 늦게 일을 시작할 수 있는 시간을 출력하는 문제이다.

 

문제 해결 방법

1. 끝나는 시간(Si)을 기준으로 정렬한다.

2. 정렬된 큐를 바탕으로 걸리는 시간(Ti)을 누적해서 더한다.(끝나는 시간과 비교)

 

Si와 누적 Ti의 차이가 가장 작은 값이 최대한 늦게 일을 시작할 수 있는 시간을 의미한다.

 

 

만약 Si와 누적 Ti의 차이가 음수가 나오면 0시에 시작해도 시간 안에 일을 못 끝낸다.

 

#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;
priority_queue <pair<int,int> > Q;

int main(void)
{
	int N=0;
	
	cin>>N;
	
	for(int i=0; i<N; i++)
	{
		int num1=0;
		int num2=0;
		cin>>num1>>num2;
		Q.push(make_pair(-num2,num1));
	}
	
	int sum=0;
	int min=987654321;

	while(!Q.empty())
	{
		int endtime=-Q.top().first;
		sum=sum+Q.top().second;
		Q.pop();
		if(min>endtime-sum)
		{
			min=endtime-sum;
		}	
	}
	if(min<0)
	{
		cout<<-1;
	}
	else
	{
		cout<<min;
	}
	
	return 0;
}