1931会議室の手配

11792 ワード
白駿 テキストリンク

これはグリディの問題で、会議の時間を一列に並べて解決する方法を考えなければならない.
私は会議が始まる時間を基準にして解いた.
問題のテストケースを例に挙げます.
11
0 6
1 4
2 13
3 5
3 8
5 7
5 9
6 10
8 11
8 12
1214のように、会議開始時間を基準に並べ替えられる.
そして最初から探し始める
会議の終了時間が前回の会議の終了時間よりも速ければ
ミーティングの選択(ミーティングカウントを計算しない)
そうでなければ、会議が開始時間より遅れたら
会議の数をかぞえる

上の箱の長さが会議の時間である場合、
グリディ方式では、もちろん迅速に終わる会議を選ぶのが有利です.
コード#コード#
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
	int n;
	cin >> n;

	vector<pair<int, int>> roomTime(n);

	for (int i = 0; i < n; i++)
		cin >> roomTime[i].first >> roomTime[i].second;


	sort(roomTime.begin(), roomTime.end());

	int finishTime = -1;
	int maxNum = 0;

	for (int i = 0; i < n; i++)
	{
		if (finishTime > roomTime[i].second)
			finishTime = roomTime[i].second;


		else
		{
			if (finishTime <= roomTime[i].first)
			{
				maxNum++;
				finishTime = roomTime[i].second;
			}
		}

	}

	cout << maxNum;


}
しかし、他の草を見て、会議が終わった時間によって並べ替えました.
もっと簡単に解けた.

会議の終了時間に従ってソートします.
最初から試して、会議が終わったら、次の会議を行う時間があれば、選択します.
これはもっと簡単です.
コード#コード#
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

bool cmp(pair<int, int> a, pair<int, int> b)
{
	if (a.second == b.second)
		return a.first < b.first;

	return a.second < b.second;
}

int main()
{
	int n;
	cin >> n;

	vector<pair<int, int>> roomTime(n);

	for (int i = 0; i < n; i++)
		cin >> roomTime[i].first >> roomTime[i].second;


	sort(roomTime.begin(), roomTime.end(),cmp);

	int finishTime = -1;
	int maxNum = 0;

	
	
	for (int i = 0; i < n; i++)
	{
		
			if (finishTime <= roomTime[i].first)
			{
				maxNum++;
				finishTime = roomTime[i].second;
			}
		

	}

	cout << maxNum;
	

}
[BOJ]2857号:FBI
コトリン鋳造、is、as