智能家居模式调度优化[200分]

题目内容

在一个智能家居系统中，用户可以设置多个“自动化联动”模式。每个模式 models[i] = [start_time, end_time, power] 描述如下：

• 模式在左闭右开区间 [start_time, end_time)（单位：秒）内处于运行状态
• 为了简化处理，start_time 和 end_time 已转化为相对于系统启动初始时间点的秒数
• 运行期间，每秒消耗固定功率 power

已知家里电网的最高承受功率 max_power。若同一时刻有多个模式同时运行，则总功率为各模式功率之和。如果总功率大于 max_power，则会导致跳闸。

系统允许永久删除（关闭）任意若干个模式，使剩余模式在任意时刻同时运行时永不跳闸。请你计算：最少需要删除多少个模式？

输入描述

• max_power：整数代表用户电网能承受的最大总电功率，取值 $1 \le max_power \le 10^5$
• modes：二维数组，每个子数组 models[i] = [start_time, end_time, power] 表示第 $i$ 个智能模式的启动时间、结束时间以及运行它所需要的电功率。
  • start_time 和 end_time：取值 $0 \le start_time < end_time \le 10^5$
  • power：取值 $1 \le power \le 10^4$
• 模式数量取值 $1 \le n \le 22$

输出描述

最少需要删除的模式个数。

样例

样例 1

输入

10
0,500,5 400,600,7 550,700,4

输出

1

说明：

• 最高承受功率 max_power 为 10
• 模式 0 在时间范围 $[0,500)$ 运行，功率 5
• 模式 1 在时间范围 $[400,600)$ 运行，功率 7
• 模式 2 在时间范围 $[550,700)$ 运行，功率 4
• 在 $(400,500)$ 区间内，模式 0 和 1 同时运行，功率 $5+7=12>10$，发生跳闸
• 删除 1 个模式即可避免（删除模式 1，保留 0 和 2）

样例 2

输入

10
0,300,5 400,600,7 700,900,3

输出

0

说明： 3 个模式时间上互不重叠，可同时安全运行。

样例 3

输入

10
0,10,6 0,10,6

输出

1

说明： 两个模式完全重叠，功率均为 6，同时运行为 $12>10$，必须删除一个。

代码

const readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
});

rl.on('line', (input) => {
    const max_power = Number(input);
    rl.on('line', (input) => {
        const modes = input.split(' ').map(v => v.split(',').map(Number));
        // console.log(max_power, modes);
        function minDeletions(maxPower, modes) {
            const n = modes.length;
            const temp = modes.filter(item => item[2] <= maxPower);
            let count = n - temp.length;
            if (temp.length <= 1) return count;
            
            const deleted = new Set();
            
            while (true) {
                // 1. 找所有冲突区间
                const conflicts = [];
                for (let i = 0; i < temp.length; i++) {
                    if (deleted.has(i)) continue;
                    
                    for (let j = i + 1; j < temp.length; j++) {
                        if (deleted.has(j)) continue;
                        
                        const [s1, e1, p1] = temp[i];
                        const [s2, e2, p2] = temp[j];
                        
                        // 判断是否重叠
                        if (s1 < e2 && s2 < e1) {
                            const overlapStart = Math.max(s1, s2);
                            const overlapEnd = Math.min(e1, e2);
                            
                            // 找出所有在这个重叠区间运行的模式
                            const items = [];
                            for (let k = 0; k < temp.length; k++) {
                                if (deleted.has(k)) continue;
                                const [s, e, p] = temp[k];
                                if (s < overlapEnd && e > overlapStart) {
                                    items.push({ idx: k, power: p });
                                }
                            }
                            
                            const totalPower = items.reduce((sum, item) => sum + item.power, 0);
                            if (totalPower > maxPower) {
                                conflicts.push({ items, totalPower });
                            }
                        }
                    }
                }
                
                if (conflicts.length === 0) break;
                
                // 2. 在所有冲突中找功率最大的
                let maxPowerIdx = -1;
                let maxPowerVal = -1;
                
                for (const conflict of conflicts) {
                    for (const item of conflict.items) {
                        if (item.power > maxPowerVal) {
                            maxPowerVal = item.power;
                            maxPowerIdx = item.idx;
                        }
                    }
                }
                
                // 3. 删除它
                if (maxPowerIdx !== -1) {
                    deleted.add(maxPowerIdx);
                    count++;
                } else {
                    break;
                }
            }
            
            return count;
        }
        const ans = minDeletions(max_power, modes);
        console.log(ans);
    })
})