首页 > 猿辅导8.1 笔试 第1题 双指针解法
头像
jhzhu1996
编辑于 2020-08-01 20:58
+ 关注

猿辅导8.1 笔试 第1题 双指针解法

将开始时间和结束时间单独计算,类似于合并两个有序数组,当开始时间小于结束时间则当前上的课 + 1,反之 - 1.取过程中的最大值即可。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;


int main()
{
	int courseNums;
	cin >> courseNums;
	vector<int> startTime;
	vector<int> endTime;
	for (int i = 0; i < courseNums; ++i) {
		int numValue = 0;
		cin >> numValue;
		startTime.push_back(numValue);
		cin >> numValue;
		endTime.push_back(numValue);
	}
	sort(startTime.begin(), startTime.end(), less<int>());
	sort(endTime.begin(), endTime.end(), less<int>());
	int start = 0, end = 0;
	int K = 0;
	int tempK = 0;
	while (start < courseNums) {
		if (startTime[start] < endTime[end]) {
			start++;
			tempK++;
		}
		else {
			end++;
			tempK--;
		}
		K = max(K, tempK);
	}
	cout << K << endl;
	return 0;
}


全部评论

(4) 回帖
加载中...
话题 回帖

相关热帖

近期热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐