papamelon 212. 区间调度问题（挑战程序设计竞赛）

本文主要是介绍papamelon 212. 区间调度问题（挑战程序设计竞赛），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

地址 https://www.papamelon.com/problem/212

解答
贪心算法
选择符合条件中区间结束比较早的那个区间。
可以证明，同样的选择区间中，选择较早结束的区间至少不会得到比选择较晚结束的区间更差的结果。
基于以上规则，我们将区间按照结束时间排序。
每次选择起始时间比当前结束时间小的区间，该区间是可以选择的区间中结束时间最早的。即可

// 1123555.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <algorithm>

using namespace std;
/*
5
1 99
2 5
4 7
6 9
8 10
输出
3
*/

const int N = 100010;
struct Node {
	int l; int r;
}node[N];
int n;

bool cmp(const struct Node& a, const struct Node& b) {
	return a.r < b.r;
}

void solve() {
	sort(node, node + n, cmp);

	int currEnd = -9999999;
	int ans = 0;
	for (int i = 0; i < n; i++) {
		if (currEnd < node[i].l) {
			ans++; currEnd = node[i].r;
		}
	}

	cout << ans << endl;

	return ;
}

int main()
{
	while (cin >> n) {
		for (int i = 0; i < n; i++) {
			int a, b;
			cin >> a >> b;
			if (a > b) { swap(a, b); }
			node[i].l = a; node[i].r = b;
		}

		solve();
	}

	return 0;
}

我的视频题解空间

这篇关于papamelon 212. 区间调度问题（挑战程序设计竞赛）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！