题解 | 组件灰度发布

解题思路

本题要求将多个用户ID范围和对应的组件ID进行合并和拆分，以便输出每个范围及其对应的组件列表。我们可以通过以下步骤实现：

数据结构：使用Pair类来存储用户ID范围的起始位置和对应的组件ID。
输入处理：读取输入并将每个范围存储在两个列表中，分别用于起始位置和结束位置。
排序：对起始位置和结束位置的列表进行排序，以便于后续的合并和拆分操作。
合并与拆分：使用两个指针遍历起始和结束位置的列表，动态维护当前的活动范围，并在适当的时候输出合并后的结果。

代码

c++
java
python

#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <string>
#include <sstream>
using namespace std;

// 用户ID范围的起始或结束位置和组件ID
struct Pair {
    int x;
    int id;
    Pair(int x, int id) : x(x), id(id) {}
};

class Main {
private:
    static vector<Pair> leftList;  // 存储起始位置
    static vector<Pair> rightList; // 存储结束位置
    static deque<int> queue;       // 活动范围队列
    static set<int> res;          // 当前活动的组件ID集合

    // 输出结果
    static void prtRes() {
        if (queue.size() == 2) {
            if (queue.front() > queue.back() - 1 || res.empty()) {
                queue.pop_front();
                return;
            }
            cout << queue.front() << " " << queue.back() - 1;
            for (int id : res) {
                cout << " " << id;
            }
            cout << endl;
            queue.pop_front();
        }
    }

    // 处理起始位置
    static void optLeft(int i) {
        queue.push_back(leftList[i].x);
        prtRes();
        res.insert(leftList[i].id);
    }

    // 处理结束位置
    static void optRight(int j) {
        queue.push_back(rightList[j].x + 1);
        prtRes();
        res.erase(rightList[j].id);
    }

public:
    static void solve() {
        string line;
        // 读取输入
        while (getline(cin, line)) {
            if (line.empty()) break;
            stringstream ss(line);
            int left, right, id;
            ss >> left >> right >> id;
            leftList.emplace_back(left, id);
            rightList.emplace_back(right, id);
        }

        // 对起始位置和结束位置进行排序
        sort(leftList.begin(), leftList.end(), 
            [](const Pair& a, const Pair& b) { return a.x < b.x; });
        sort(rightList.begin(), rightList.end(), 
            [](const Pair& a, const Pair& b) { return a.x < b.x; });

        int i = 0, j = 0, n = leftList.size();
        // 合并范围
        while (i < n && j < n) {
            if (leftList[i].x <= rightList[j].x) {
                optLeft(i++);
            } else {
                optRight(j++);
            }
        }
        // 处理剩余的范围
        while (i < n) optLeft(i++);
        while (j < n) optRight(j++);
    }
};

// 静态成员变量的定义
vector<Pair> Main::leftList;
vector<Pair> Main::rightList;
deque<int> Main::queue;
set<int> Main::res;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    Main::solve();
    return 0;
}

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

class Pair {
    int x; // 用户ID范围的起始或结束位置
    int id; // 组件ID

    Pair(int x, int id) {
        this.x = x;
        this.id = id;
    }
}

public class Main {
    static ArrayList<Pair> leftList = new ArrayList<>(); // 存储起始位置
    static ArrayList<Pair> rightList = new ArrayList<>(); // 存储结束位置
    static LinkedList<Integer> queue = new LinkedList<>(); // 活动范围队列
    static TreeSet<Integer> res = new TreeSet<>(); // 当前活动的组件ID集合

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line;

        // 读取输入
        while ((line = br.readLine()) != null) {
            String[] str = line.split(" ");
            int left = Integer.parseInt(str[0]);
            int right = Integer.parseInt(str[1]);
            int id = Integer.parseInt(str[2]);
            leftList.add(new Pair(left, id));
            rightList.add(new Pair(right, id));
        }

        // 对起始位置和结束位置进行排序
        leftList.sort(Comparator.comparingInt(o -> o.x));
        rightList.sort(Comparator.comparingInt(o -> o.x));

        int i = 0, j = 0, n = leftList.size();
        // 合并范围
        while (i < n && j < n) {
            if (leftList.get(i).x <= rightList.get(j).x) {
                optLeft(i++);
            } else {
                optRight(j++);
            }
        }
        // 处理剩余的范围
        while (i < n) optLeft(i++);
        while (j < n) optRight(j++);
    }

    // 处理起始位置
    private static void optLeft(int i) {
        queue.offer(leftList.get(i).x);
        prtRes();
        res.add(leftList.get(i).id);
    }

    // 处理结束位置
    private static void optRight(int j) {
        queue.offer(rightList.get(j).x + 1);
        prtRes();
        res.remove(rightList.get(j).id);
    }

    // 输出结果
    private static void prtRes() {
        if (queue.size() == 2) {
            if (queue.peekFirst() > queue.peekLast() - 1 || res.isEmpty()) {
                queue.pop();
                return;
            }
            StringBuilder sb = new StringBuilder();
            sb.append(queue.peekFirst()).append(" ").append(queue.peekLast() - 1);
            for (Integer id : res) {
                sb.append(" ").append(id);
            }
            System.out.println(sb);
            queue.pop();
        }
    }
}

from collections import deque
from typing import List, Set

class Pair:
    def __init__(self, x: int, id: int):
        self.x = x  # 用户ID范围的起始或结束位置
        self.id = id  # 组件ID

class Main:
    # 静态成员变量
    leftList: List[Pair] = []  # 存储起始位置
    rightList: List[Pair] = []  # 存储结束位置
    queue: deque = deque()  # 活动范围队列
    res: Set[int] = set()  # 当前活动的组件ID集合

    @staticmethod
    def prt_res() -> None:
        """输出结果"""
        if len(Main.queue) == 2:
            if Main.queue[0] > Main.queue[1] - 1 or not Main.res:
                Main.queue.popleft()
                return
            
            result = f"{Main.queue[0]} {Main.queue[1] - 1}"
            for id in sorted(Main.res):  # 使用sorted确保组件ID有序输出
                result += f" {id}"
            print(result)
            Main.queue.popleft()

    @staticmethod
    def opt_left(i: int) -> None:
        """处理起始位置"""
        Main.queue.append(Main.leftList[i].x)
        Main.prt_res()
        Main.res.add(Main.leftList[i].id)

    @staticmethod
    def opt_right(j: int) -> None:
        """处理结束位置"""
        Main.queue.append(Main.rightList[j].x + 1)
        Main.prt_res()
        Main.res.remove(Main.rightList[j].id)

    @staticmethod
    def solve() -> None:
        # 读取输入
        while True:
            try:
                line = input().strip()
                if not line:
                    break
                left, right, id = map(int, line.split())
                Main.leftList.append(Pair(left, id))
                Main.rightList.append(Pair(right, id))
            except EOFError:
                break

        # 对起始位置和结束位置进行排序
        Main.leftList.sort(key=lambda x: x.x)
        Main.rightList.sort(key=lambda x: x.x)

        i, j = 0, 0
        n = len(Main.leftList)

        # 合并范围
        while i < n and j < n:
            if Main.leftList[i].x <= Main.rightList[j].x:
                Main.opt_left(i)
                i += 1
            else:
                Main.opt_right(j)
                j += 1

        # 处理剩余的范围
        while i < n:
            Main.opt_left(i)
            i += 1
        while j < n:
            Main.opt_right(j)
            j += 1

if __name__ == "__main__":
    Main.solve()

算法及复杂度

算法：使用双指针法合并和拆分用户ID范围。
时间复杂度： $O(n \log n)$ ，其中 $n$ 是输入范围的数量，主要用于排序。
空间复杂度： $O(n)$ ，用于存储起始和结束位置的列表。