package arrays;

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

/**
 * 题目:合并数组区间
 * y:
 * 1 8
 * 2 4
 * 9 10
 * 10 16
 * 合并后: 1 8
 * 9 16
 * @Author Gavin
 * @date 2022年01月03日 15:00
 */
public class array_13 {
 /**
 * 解题思路:
 * 首先按照各个区间的start开始排序
 * 然后取出最后一个间进行比较start和end
 * 如果第一个的end大于第二个的start,小于第二个的end,那么就更新第一个的
 * end为第二个的end
 */
 public class Interval{
 int start;
 int end;
 Interval(){start=0;end=0;}
 Interval(int s,int e){start=s;end=e;}
 }
 //Time:O(n*log(n)) Space:O(1)
 public List<Interval> merge(List<Interval> intervals){
 List<Interval> result=new ArrayList<>();
 //首先对list里面的元素按照start进行排序
 //这一步是关节点,主要就是排序
 intervals.sort((a,b)->a.start-b.start);
 for(Interval pre:intervals){
 int n=result.size();
 if(result.isEmpty()||result.get(n-1).end<pre.start){
 result.add(pre);
 }else{
 result.get(n-1).end=Math.max(result.get(n-1).end,pre.end);
 }
 }
 return result;
 }
}