2054.两个最好的不重叠活动

/*
 * @lc app=leetcode.cn id=2054 lang=typescript
 *
 * [2054] 两个最好的不重叠活动
 */

// @lc code=start

/* 暴力法：复杂度很高 */
// function maxTwoEvents(events: number[][]): number {
// 	// 先按开始时间排序
// 	events = events.sort((a, b) => a[0] - b[0]);
// 	let maxValue = 0; // 最大收益
// 	for (let i = 0; i < events.length; i++) {
// 		let current = events[i];
// 		let currentMax = 0;
// 		// 过滤掉开始时间小于当前结束时间的项
// 		let others = events.slice(i + 1).filter(el => el[0] > current[1]);

// 		if (others.length == 0) {
// 			// 不存在其他项
// 			currentMax = Math.max(current[2], currentMax);
// 		} else {
// 			for (let j = 0; j < others.length; j++) {
// 				currentMax = Math.max(currentMax, current[2] + others[j][2]);
// 			}
// 		}

// 		maxValue = Math.max(maxValue, currentMax);
// 	}
// 	return maxValue;
// }

/* 暴力法2：复杂度很高 */
// function maxTwoEvents(events: number[][]): number {
// 	// 先按开始时间排序
// 	events = events.sort((a, b) => b[0] - a[0]);
// 	let maxValue = 0; // 最大收益
// 	for (let i = 0; i < events.length; i++) {
// 		let current = events[i];
// 		let currentMax = 0;
// 		// 过滤掉开始时间小于当前结束时间的项
// 		let others = events.slice(i + 1).filter(el => el[1] < current[0]);

// 		if (others.length == 0) {
// 			// 不存在其他项
// 			currentMax = Math.max(current[2], currentMax);
// 		} else {
// 			currentMax = Math.max(currentMax, current[2] + others[0][2]);
// 		}

// 		maxValue = Math.max(maxValue, currentMax);
// 	}
// 	return maxValue;
// }

/* 二分查找法 */
function maxTwoEvents(events: number[][]): number {
	const n = events.length;

	// 1. 按开始时间排序（关键！保证二分查找后的所有活动开始时间都 > target）
	events.sort((a, b) => a[0] - b[0]);

	// 2. 预处理后缀最大值：suffixMax[i] = 从位置i到末尾的最大value
	const suffixMax: number[] = new Array(n);
	suffixMax[n - 1] = events[n - 1][2];
	for (let i = n - 2; i >= 0; i--) {
		suffixMax[i] = Math.max(suffixMax[i + 1], events[i][2]);
	}

	// 3. 二分查找：找第一个开始时间 > target 的位置
	function binarySearch(target: number): number {
		let left = 0,
			right = n;
		while (left < right) {
			const mid = Math.floor((left + right) / 2);
			if (events[mid][0] > target) {
				right = mid;
			} else {
				left = mid + 1;
			}
		}
		return left;
	}

	// 4. 遍历每个活动，计算最大收益
	let ans = suffixMax[0]; // 至少选一个活动的最大值
	for (let i = 0; i < n; i++) {
		const endTime = events[i][1];
		const value = events[i][2];

		// 找第一个开始时间 > 当前结束时间的活动
		const j = binarySearch(endTime);
		if (j < n) {
			// 存在可配对的活动
			ans = Math.max(ans, value + suffixMax[j]);
		}
	}

	return ans;
}

// data
let events = [
	[1, 3, 2],
	[4, 5, 2],
	[2, 4, 3],
];
console.log("最大活动收益：", maxTwoEvents(events));

// @lc code=end