温度区间分组算法[修订版]：最优温度设定点非暴力求解方法问询

核心思路拆解 #

要解决这个问题，我们可以分两步精准处理：先找到覆盖物品数量最多的温度区间，再在这些区间内筛选出缓冲空间最大的温度点。因为最优温度的候选只会出现在所有物品的min_temp、max_temp这些关键节点，或是节点之间的连续区间中，完全不需要暴力遍历所有温度值。

第一步：找出覆盖物品最多的温度区间 #

事件点排序法 #

1. 把每个物品的min_temp标记为进入事件（记为+1，表示该温度开始覆盖这个物品），max_temp标记为离开事件（记为-1，表示该温度结束覆盖这个物品）。
2. 对所有事件点按温度值排序：
   • 若两个事件温度相同，离开事件必须排在进入事件前面（比如物品A的max_temp和物品B的min_temp相等时，该温度属于B但不属于A，先处理离开能保证计数准确）。
3. 遍历排序后的事件点，维护当前覆盖的物品数量current_count，记录过程中的max_count（最大覆盖数），同时收集所有达到max_count的连续温度区间。

举个简单示例：

• 物品A：[0, 10]、物品B：[5, 15]、物品C：[3, 8]
• 排序后的事件列表：(0, +1)、(3, +1)、(5, +1)、(8, -1)、(10, -1)、(15, -1)
• 遍历后覆盖数变化：1→2→3→2→1→0，其中max_count=3，对应的最优区间是[5,8]

时间复杂度 #

该步骤的时间复杂度为O(N log N)，主要来自事件点的排序，远优于暴力遍历的O(N*M)（M为温度步长次数），完全适配N庞大的场景。

第二步：在最优覆盖区间内找缓冲最大的点 #

拿到所有覆盖数等于max_count的区间后，按以下规则筛选最优温度：

1. 单个连续区间[L, R]：
   • 区间内所有温度都能覆盖max_count个物品，其中缓冲空间最大的点是区间中点：(L + R)/2。此时该点到区间两端的距离相等，是温度波动时最安全的位置（缓冲值为(R-L)/2）。
2. 多个不连续的最优区间：
   • 计算每个区间的缓冲值(R-L)/2，选择缓冲值最大的区间中点；若多个区间缓冲值相同，任选其一即可。

特殊情况处理 #

• 若最优覆盖数对应的是单个点（比如多个物品的min和max刚好交汇在某一点），则该点就是唯一候选，缓冲值为0；
• 若最优区间由多个事件点构成连续区间，直接取中点即可。

完整流程代码示例 #

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

using namespace std;

struct Event {
    float temp;
    int delta; // +1 对应min_temp，-1 对应max_temp
};

bool compareEvents(const Event& e1, const Event& e2) {
    if (e1.temp != e2.temp) {
        return e1.temp < e2.temp;
    }
    // 温度相同时，离开事件优先排序
    return e1.delta < e2.delta;
}

pair<float, size_t> findOptimalTemp(const vector<pair<float, float>>& items) {
    vector<Event> events;
    for (const auto& item : items) {
        events.push_back({item.first, 1});
        events.push_back({item.second, -1});
    }

    sort(events.begin(), events.end(), compareEvents);

    size_t current_count = 0;
    size_t max_count = 0;
    float interval_start = 0.0f;
    vector<pair<float, float>> optimal_intervals;

    for (size_t i = 0; i < events.size(); ++i) {
        const Event& e = events[i];
        // 记录当前处于max_count的区间
        if (current_count == max_count && i > 0 && events[i-1].temp < e.temp) {
            optimal_intervals.emplace_back(interval_start, events[i-1].temp);
        }

        current_count += e.delta;

        // 更新最大覆盖数与区间起点
        if (current_count > max_count) {
            max_count = current_count;
            optimal_intervals.clear();
            interval_start = e.temp;
        } else if (current_count == max_count && i == 0) {
            interval_start = e.temp;
        }
    }
    // 处理最后一个区间
    if (current_count == max_count && !events.empty()) {
        optimal_intervals.emplace_back(interval_start, events.back().temp);
    }

    // 筛选缓冲最大的区间
    float best_temp = 0.0f;
    float max_buffer = -1.0f;
    for (const auto& interval : optimal_intervals) {
        float L = interval.first;
        float R = interval.second;
        float buffer = (R - L) / 2;
        if (buffer > max_buffer) {
            max_buffer = buffer;
            best_temp = (L + R) / 2;
        }
    }

    return {best_temp, max_count};
}

int main() {
    vector<pair<float, float>> items = {{0,10}, {5,15}, {3,8}, {6,12}};
    auto [temp, count] = findOptimalTemp(items);
    cout << "最优温度: " << temp << ", 覆盖物品数: " << count << endl;
    return 0;
}

方法优势 #

• 效率极高：O(N log N)时间复杂度，适配百万级以上的物品数量；
• 结果精准：直接锁定所有候选区间，不会因步长遗漏最优解；
• 兼顾需求：同时满足覆盖物品最多、缓冲空间最大两个核心要求。

内容的提问来源于stack exchange，提问作者Jordan