NC37 合并区间

Dear 丶 2024-03-27 14:25 1阅读 0赞

> [牛客华为机试题库【题号 HJ开头】（重点看）][HJ]  
> [牛客在线编程算法篇【题号NC开头】][NC]  
> [剑指offer【题号 JZ开头】][offer_ JZ]  
> [力扣][Link 1]

### 1）[原题链接][Link 2] ###

### 2）已有题解 ###

### 3）代码 ###

package array;
    
    import java.io.IOException;
    import java.util.ArrayList;
    import java.util.List;
    import java.util.stream.Collectors;
    
    /**
     * NC37 合并区间
     */
    public class NC37CombinedArea {
        
        public static void main(String[] args) throws IOException {
        
            ArrayList<Interval> list = new ArrayList<>();
            list.add(new Interval(10, 30));
            list.add(new Interval(20, 60));
            list.add(new Interval(80, 100));
            list.add(new Interval(150, 180));
            ArrayList<Interval> merge = merge(list);
            System.out.println(merge);
        }
    
        public static ArrayList<Interval> merge(ArrayList<Interval> intervals) {
        
            if (intervals.size() <= 1) {
        
                return intervals;
            }
    
            // 两个指标都排序排序
            List<Interval> orderedIntervals = intervals.stream().sorted((a, b) -> {
        
                if (a.start == b.start) {
        
                    return a.end - b.end;
                } else {
        
                    return a.start - b.start;
                }
            }).collect(Collectors.toList());
    
    
            // 基底
            Interval base = orderedIntervals.get(0);
    
            ArrayList<Interval> res = new ArrayList<>();
            for (int i = 1; i < orderedIntervals.size(); i++) {
        
                if (isNotUnit(base, orderedIntervals.get(i))) {
        
                    res.add(base); // 不相交，收集基底
                    base = orderedIntervals.get(i); // 变基
                } else {
        
                    base = getNew(base, orderedIntervals.get(i)); // 当前区间和Base区间取并集
                }
                if (i == orderedIntervals.size() - 1) {
         // 当前项为最后一项的话、直接收集起来
                    res.add(base);
                }
            }
            return res;
        }
    
        /**
         * 判断两个区间不想交
         */
        public static boolean isNotUnit(Interval left, Interval right) {
        
            return left.end < right.start;
        }
    
        /**
         * 获取最大区间
         */
        public static Interval getNew(Interval left, Interval right) {
        
            int min = Math.min(left.start, right.start);
            int max = Math.max(left.end, right.end);
            return new Interval(min, max);
        }
    
    }
    
    class Interval {
        
        int start;
        int end;
    
        Interval() {
        
            start = 0;
            end = 0;
        }
    
        Interval(int s, int e) {
        
            start = s;
            end = e;
        }
    
        @Override
        public String toString() {
        
            return "[" + start + "," + end + ']';
        }
    }

[HJ]: https://www.nowcoder.com/exam/oj/ta?tpId=37
[NC]: https://www.nowcoder.com/exam/oj
[offer_ JZ]: https://www.nowcoder.com/exam/oj/ta?page=1&tpId=13&type=13
[Link 1]: https://leetcode.cn/problemset/all/
[Link 2]: https://www.nowcoder.com/practice/69f4e5b7ad284a478777cb2a17fb5e6a?tpId=117&tqId=37737&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=/exam/oj?page=1&pageSize=50&search=37&tab=%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587&topicId=117&difficulty=undefined&judgeStatus=undefined&tags=&title=37