核心代码编程-最大化游戏试玩资格分发-100分

题目描述： 新研发了一台游戏设备可以面向用户接受试玩。现有n个试玩申请，每个试玩有开始时间和结束时间。
作为协调员，为了能让更多的人体验到游戏，你需要对试玩申请进行选择，使得：
1．任意两个被选中的试玩时间不重叠。
2．任意两个被选中的试玩时间允许连续，例如［2,3］和［3,4］认为是可以都被安排的。
3．被安排的试玩数量最大化
请问最多能安排多少场试玩？
输入：
第一行：一个整数n(1sn≤10°)，表示试玩申请数量
第二行：是一个长度为n的数组，数组的每个元素为两个整数 start和end (0 s start < end ≤ 10°)，表示试玩的开始和结束时间
输出：
一个整数，表示最多能安排的试玩数量
补充说明：
示例1
输入：3,[[1.5].[2.3].[4.6]]
输出：2
说明：选择玩家［2,3],[4,6]，共2位
如果选择［1,5］则跟其他的时间冲突，则只有1位不满足最多玩家的要求
示例2
输入：5,[[1.2],[3,4], [5,6],[7,8], [9, 101]
输出：5
说明：共有5个试玩申请，且时间都不重合，允许连续，因此最多可以安排5个试玩。
示例3
输入： 1,[[1. 5]]
输出：1
说明： 只有一个试玩申请，直接安排
示例4
输入：3,[[1.5].[2,4].[3.6]]
输出：1
说明： 所有试玩时间都冲突，只能安排一场

贪心算法解决方案

这是一个经典的活动选择问题（Activity Selection Problem），使用贪心算法解决。核心策略是优先选择结束时间最早的活动，为后续活动留出更多时间。算法步骤如下：

1. 按结束时间升序排序所有活动
2. 选择结束时间最早的活动
3. 从剩余活动中选择第一个开始时间≥上次选择结束时间的活动
4. 重复步骤3直到遍历完所有活动

时间复杂度：$O(n \log n)$（排序主导）

C语言实现

#include <stdlib.h> int cmp(const void *a, const void *b) { int *x = *(int **)a, *y = *(int **)b; return x[1] - y[1]; } int maxEvents(int n, int** intervals) { qsort(intervals, n, sizeof(int*), cmp); int count = 0, lastEnd = -1; for (int i = 0; i < n; i++) { if (intervals[i][0] >= lastEnd) { count++; lastEnd = intervals[i][1]; } } return count; }

C++实现

#include <vector> #include <algorithm> using namespace std; int maxEvents(vector<vector<int>>& intervals) { sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b) { return a[1] < b[1]; }); int count = 0, lastEnd = -1; for (auto& itv : intervals) { if (itv[0] >= lastEnd) { count++; lastEnd = itv[1]; } } return count; }

JavaScript实现

function maxEvents(intervals) { intervals.sort((a, b) => a[1] - b[1]); let count = 0, lastEnd = -1; for (const [start, end] of intervals) { if (start >= lastEnd) { count++; lastEnd = end; } } return count; }

Java实现

import java.util.Arrays; public class Solution { public int maxEvents(int[][] intervals) { Arrays.sort(intervals, (a, b) -> a[1] - b[1]); int count = 0, lastEnd = -1; for (int[] itv : intervals) { if (itv[0] >= lastEnd) { count++; lastEnd = itv[1]; } } return count; } }

Go实现

import "sort" func maxEvents(intervals [][]int) int { sort.Slice(intervals, func(i, j int) bool { return intervals[i][1] < intervals[j][1] }) count, lastEnd := 0, -1 for _, itv := range intervals { if itv[0] >= lastEnd { count++ lastEnd = itv[1] } } return count }

Python实现

def maxEvents(intervals): intervals.sort(key=lambda x: x[1]) count, last_end = 0, -1 for start, end in intervals: if start >= last_end: count += 1 last_end = end return count

所有实现均遵循以下原则：

1. 按结束时间升序排序
2. 贪心选择兼容活动
3. 时间复杂度 $O(n \log n)$
4. 空间复杂度 $O(1)$（除排序外）