美文网首页
编程题:合并区间

编程题:合并区间

作者: 爱读书的夏夏 | 来源:发表于2020-02-19 21:48 被阅读0次

    给出一个区间的集合,请合并所有重叠的区间。
    输入: [[1,3],[2,6],[8,10],[15,18]]
    输出: [[1,6],[8,10],[15,18]]
    解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

    public class MySet {
        int left;
        int right;
    
        public MySet(){
    
        }
    
        public MySet(int left,int right){
            this.left = left;
            this.right = right;
        }
    
        public int getLeft() {
            return left;
        }
    
        public void setLeft(int left) {
            this.left = left;
        }
    
        public int getRight() {
            return right;
        }
    
        public void setRight(int right) {
            this.right = right;
        }
    }
    

    解法:

       public static  List<MySet> mergeSet(List<MySet> theSets) {
    
            if (theSets == null || theSets.size() <= 1) {
                return theSets;
            }
            List<MySet> result = new ArrayList<>();
    
    
            theSets.sort((set1,set2)->{
                return set1.getLeft() - set2.getLeft();
            });
    
            MySet mySet = theSets.get(0);
            for (int i = 1; i < theSets.size(); i++){
                if (!(mySet.getRight() < theSets.get(i).getLeft())){
                    mySet.setRight(Math.max(mySet.getRight(),theSets.get(i).getRight()));
                } else {
                    result.add(mySet);
                    mySet = theSets.get(i);
                }
            }
            //最后一定要将最后合并的元素加入到结果中。否则会丢失元素。
            result.add(mySet);
    
            return result;
        }
    
    
    
       public static void main(String[] args) {
            MySet mySet1 = new MySet(1,4);
            MySet mySet2 = new MySet(2,6);
            MySet mySet3 = new MySet(8,10);
            MySet mySet4 = new MySet(12,13);
            MySet mySet5 = new MySet(16,19);
    
            List<MySet> mySets = new LinkedList<>();
            mySets.add(mySet1);
            mySets.add(mySet2);
            mySets.add(mySet3);
            mySets.add(mySet4);
            mySets.add(mySet5);
            List<MySet> result = mergeSet(mySets);
            System.out.println(JSONObject.toJSONString(result));
        }
    
    

    输出结果:

    [{"left":1,"right":6},{"left":8,"right":10},{"left":12,"right":13},{"left":16,"right":19}]
    
    

    相关文章

      网友评论

          本文标题:编程题:合并区间

          本文链接:https://www.haomeiwen.com/subject/hwmzfhtx.html