字节跳动2019届校招笔试题二

2.为了提高文章质量，每一篇文章（假设全部都是英文）都会有m民编辑进行审核，每个编辑独立工作，会把觉得有问题的句子通过下表记录下来，比如[1,10]，1表示病句的第一个字符，10表示病句的最后一个字符。也就是从1到10着10个字符组成的句子，是有问题的。

现在需要把多名编辑有问题的句子合并起来，送个总编辑进行最终的审核。比如编辑A指出的病句是[1,10]，[32,45];编辑B指出的病句是[5,16]，[78,94]那么[1,10]和[5,16]是有交叉的，可以合并成[1,16][32,45][78,94]

输入描述：

编辑数量m，之后每行是每个编辑的标记的下表组合，第一个和最后一个下标用英文逗号分隔，每组下标之间用分号分隔

输出描述：

合并后的下标集合，第一个和最后一个下标用英文逗号分隔，每组下标之间用分号分隔。返回结果是从小到大递增排列

例：输入

3

1,10;32,45

78,94;5,16

80,100;200,220;16,32

输出： 1,45;78,100;200,220

java实现：

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Problem2 {
    static String input = "3\n" +
            "1,10;32,45\n" +
            "78,94;5,16\n" +
            "80,100;200,220;16,32";

    static class Range implements Comparable<Range>{
        private int start;
        private int end;

        public Range(int start, int end) {
            this.start = start;
            this.end = end;
        }

        @Override
        public String toString() {
            return start +"," + end +";";
        }

        @Override
        public int compareTo(Range o) {
            return start - o.start;
        }

        public boolean isCombine(Range o){
            return end+1 >= o.start;
        }

        public Range combine(Range o){
            if(isCombine(o)){
                start = Math.min(start,o.start);
                end = Math.max(end,o.end);
            }
            return this;
        }
    }

    static void handleInput(){
        String[] lines = input.split("\n");
        List<Range> ranges = new ArrayList<>(10);
        for (int i = 1 ; i < lines.length; i++) {
            String[] pairs = lines[i].split(";");
            for (String pair:
                 pairs) {
                String[] se = pair.split(",");
                ranges.add(new Range(Integer.valueOf(se[0]),Integer.valueOf(se[1])));
            }
        }
        Range[] rs = ranges.toArray(new Range[]{});
        Arrays.sort(rs);
        ranges.clear();
        Range cur,next;

        for (int i = 0; i < rs.length-1; i++) {
            cur = rs[i];
            next = rs[i+1];
            if(cur.isCombine(next)){
                rs[i+1] = cur.combine(next);
            }else{
                ranges.add(cur);
            }
//            处理最后一个
            if(i+1 == rs.length-1){
                ranges.add(rs[i+1]);
            }
        }
        StringBuilder output = new StringBuilder();
        for (Range range:
             ranges) {
            output.append(range);
        }
        System.out.println(output.substring(0,output.length()-1));

    }

    public static void main(String[] args) {
        handleInput();
    }
}