牛客在线编程101-89 合并区间

短命女 2023-10-04 19:54 2阅读 0赞

描述  
给出一组区间，请合并所有重叠的区间。  
请保证合并后的区间按区间起点升序排列。

数据范围：区间组数 0 \\le n \\le 2 \\times 10^50≤n≤2×10  
5  
，区间内 的值都满足 0 \\le val \\le 2 \\times 10^50≤val≤2×10  
5

要求：空间复杂度 O(n)O(n)，时间复杂度 O(nlogn)O(nlogn)  
进阶：空间复杂度 O(val)O(val)，时间复杂度O(val)O(val)

时间复杂度较高，需要改进

import java.util.*;
    /**
     * Definition for an interval.
     * public class Interval {
     *     int start;
     *     int end;
     *     Interval() { start = 0; end = 0; }
     *     Interval(int s, int e) { start = s; end = e; }
     * }
     */
    public class Solution {
        
        public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
        
            //排序
            Collections.sort(intervals, new Comparator<Interval>() {
        
                @Override
                public int compare(Interval o1, Interval o2) {
        
                    return o1.start - o2.start;
                }
            });
    
            //双指针，合并区间
            int pre = 0;
            int cur = 1;
            int len = intervals.size();
    
            if (len <= 1) {
        
                return intervals;
            } else {
        
                while(cur < len) {
        
                    //需要合并区间
                    if (intervals.get(pre).end >= intervals.get(cur).start) {
        
                        intervals.get(cur).start = intervals.get(pre).start;
                        intervals.get(cur).end = Math.max(intervals.get(pre).end, intervals.get(cur).end);
                        intervals.remove(pre);
                        len--;
                    } else {
        
                        pre++;
                        cur++;
                    }
                }
    
                return intervals;
            }
        }
    }