首页 > 试题广场 >

组件灰度发布

[编程题]组件灰度发布
  • 热度指数:478 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 128M,其他语言256M
  • 算法知识视频讲解
为了提高客户端开发效率和发布速度,需从客户端抽象出不同功能的组件,并且每个组件可以独立开发和发布。为实现上述功能,需要实现一个组件灰度发布服务,核心功能是
1. 按用户ID范围来灰度发布组件,例如范围a{1,10}发布组件1,范围b{5,20}发布组件2,范围c{15,25}发布组件3,其中a、b、c的范围是有可能重叠,为提高查找效率和节省空间,需对所有范围进行合并和拆分,最终输出为范围A{1,4}发布组件1,B{5,10}发布组件1和2,C{11,14}发布组件2,D{15,20}发布组件2和3,E{21,25}发布组件3

输入描述:
输入有多行,每一行表示用户ID范围和对应的组件ID


输出描述:
输出有多行,每一行表示用户ID范围和对应的组件列表,范围从小到大排序,各个数字之间用空格隔开,行末无空格
示例1

输入

1 10 1
5 20 2
15 25 3

输出

1 4 1
5 10 1 2
11 14 2
15 20 2 3
21 25 3
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

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

/**
 * @author wylu
 */
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<>();

    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]), 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(new Comparator<Pair>() {
            @Override
            public int compare(Pair o1, Pair o2) {
                return Integer.compare(o1.x, o2.x);
            }
        });
        rightList.sort(new Comparator<Pair>() {
            @Override
            public int compare(Pair o1, Pair o2) {
                return Integer.compare(o1.x, o2.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();
        }
    }
}

编辑于 2019-02-02 12:20:35 回复(2)
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef struct number{
//int Count=0;//ID数量
string Id="";
}Num;
int main()
{
    Num num[100];
    char id;
    int j=1;
    int IdFirst,IdEnd,IdMax=0,IdMin=0;
    cin>>IdFirst>>IdEnd>>id;
    IdMax = IdEnd; IdMin = IdFirst;
    for(int i=IdFirst;i<=IdEnd;i++)
    {
        //num[i].Count++;
        num[i].Id += " ";
        num[i].Id += id;
    }
    while(cin>>IdFirst>>IdEnd>>id)
    {
        j++;
        if(IdMax<IdEnd)
           IdMax = IdEnd;
        if(IdMin>IdFirst)
           IdMin = IdFirst;
        for(int i=IdFirst;i<=IdEnd;i++)
        {
            //num[i].Count++;
            num[i].Id += " ";
            num[i].Id += id;
        }
        if(j>=3)
            break;
    }
    string IDs = num[IdMin].Id;
    int Begin = IdMin,End;
    for(int k=IdMin;k<=IdMax;k++)
    {
        if(IDs!=num[k].Id)  //找到区间
        {End = k-1;
        if(num[k-1].Id!="")
        cout<<Begin<<" "<<End<<num[k-1].Id<<endl;
        Begin = k;IDs = num[k].Id; }
        if(k == IdMax)
            cout<<Begin<<" "<<k<<num[k].Id<<endl;
    }
}

发表于 2019-08-08 10:26:13 回复(1)
###范围从小到大排序应该是结束位置进行排序
###所以代码中没有进行结束位置的判断(默认了当前的结束位置大于上次的结束位置)
 
if__name__=='__main__':
    num=[]
    while1:
        try:
            tmp=list(map(int,input().split()))
            include=[]
            ###当前的起始位置大于上次的结束位置
            ifnotnum ortmp[0]>num[-1][1]:
                num.append(tmp)
            ###当前的起始位置小于上次的结束位置
            else:
                #有两个分裂操作:
                #1.截止末尾:当前num的最后位置+1
                iftmp[1]>num[-1][1]:
                    include.append([num[-1][1]+1,tmp[1],tmp[2]])
                #2.循环遍历重复段直到在num中找到tmp的起始位置
                whilenum:
                    cur=num.pop()
                    #如果当前的起始位置大于tmp的起始则是全覆盖
                    ifcur[0]>tmp[0]:
                        cur.append(tmp[2])
                        include.append(cur)
                    #否则就是在num中找到了tmp的起始位置,分裂
                    else:
                        ifcur[0]==tmp[0]:
                            cur.append(tmp[2])
                            include.append(cur)
                        else:
                            curid=cur[2:]
                            tmp1=[cur[0],tmp[0]-1]+curid
                            curid.append(tmp[2])
                            tmp2=[tmp[0],cur[1]]+curid
                            include.append(tmp2)
                            include.append(tmp1)
                        break
                ifinclude[-1][0]>tmp[0]:
                    include.append([tmp[0],include[-1][0]-1,tmp[2]])
                #把inlucde压入num
                whileinclude:
                    num.append(include.pop())
        except:
            break
    forn innum:
        print(' '.join(map(str,n)))

发表于 2019-03-24 11:44:27 回复(0)