贪心算法求解最小放映厅数量

以下是使用贪心算法求解最小放映厅数量的C++代码实现：

unsigned int intervals::solution() {
	int startiLength = starti.size();
	vector<int> endTime;//记录所需的电影厅数量，值是每部电影的结束时间，最后返回endTime的size就可以
	endTime.push_back(endi[0]);
	for (int i = 1; i < startiLength; i++) {//将排好序的电影遍历一次
		int endTimeLength = endTime.size();
		for (int j = 0; j < endTimeLength; j++) {//对于每一部电影，将每个已存在的电影厅的结束时间遍历
			if (starti[i] >= endTime[j]) {//若开始时间迟于某一已有电影厅的结束时间，
				endTime[j] = endi[i];//则更新该电影厅的结束时间并退出这层循环
				break;
			}
			if (j == endTimeLength - 1) {//若遍历到最后一个电影厅都没有找到
				endTime.push_back(endi[i]);//则增加一个新的电影厅
			}
		}		
	}
	return endTime.size();//返回电影厅的数量
}

算法分析

该算法使用贪心的思路来求解最小放映厅数。

排序: 首先对电影的开始时间进行排序。
遍历: 算法遍历排好序的电影，并使用 endTime 数组来记录所需的电影厅数量。
分配: 对于每个电影，算法遍历已存在的电影厅的结束时间，若开始时间晚于某个电影厅的结束时间，则更新该电影厅的结束时间；若遍历到最后一个电影厅仍然没有找到合适的电影厅，则增加一个新的电影厅。
结果: 最后，返回 endTime 数组的大小作为最小放映厅数。

正确性

根据算法的描述，它可以保证求出正确的最小放映厅数。通过遍历电影并更新电影厅的结束时间，算法确保不会发生时间冲突，即每个电影都能在合适的电影厅进行放映。增加新的电影厅的操作也能保证每个电影都有足够的空间进行放映，且不会与其他电影产生冲突。

时间复杂度

该算法的时间复杂度为 O(n^2)，其中 n 是电影的数量。在实际应用中，可能需要考虑优化算法的时间复杂度，以提高计算效率。