34.Merge Intervals(合并序列)

Level:

  Medium

题目描述:

Given a collection of intervals, merge all overlapping intervals.

Example 1:

Input: [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].

Example 2:

Input: [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.

思路分析:

定义一个数据类型interval

public class Interval{
    int start; //序列对的首元素
    int end;//序列对的尾元素
    public Interval(int s,int e){
        start=s;
        end=e;
    }
}

  将题目给出的所有序列对的首元素都保存在一个数组starts,将所有尾元素保存在另外一个数组ends,然后将两个数组排序,设置两个指针,i 和 j。从头开始遍历数组,如果starts[i+1]>ends[i],那么产生一个以ends[i]作为尾部的Interval,头部为starts[j],j的初始值是0,随后每产生一个Interval,j 就更新为(i+1);当i==n-1时,也会产生一个最后一个Interval。

代码:

/**
 * 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 List<Interval>merge(List<Interval>intervals){
        List<Interval>finalList=new AarryList<>();
        int []starts=new int[intervals.size()];
        int []ends=new int[intervals.size()];
        for(int i=0;i<intervals.size();i++){
            starts[i]=intervals.get(i).start;
            ends[i]=intervals.get(i).end;
        }
        Arrays.sort(starts);
        Arrays.sort(end);
        for(int i=0,j=0;i<starts.length;i++){
            if(i==n-1||starts[i+1]>ends[i]){
                Interval interval=new Interval(starts[j],ends[i]);
                finalList.add(interval);
                j=i+1;
            }
        }
        return finalList;
    }
}
上一篇:java – 精确一秒间隔的最佳计时器技术是什么?


下一篇:用Taurus.MVC 做个企业站(下)