L1-合并区间

Posted on | In |

给出若干闭合区间，合并所有重叠的部分。

样例

给出的区间列表 => 合并后的区间列表：

[ [
[1, 3], [1, 6],
[2, 6], => [8, 10],
[8, 10], [15, 18]
[15, 18] ]
]

挑战
O(n log n) 的时间和 O(1) 的额外空间。

思路

贪心法，需要依赖链表每个节点的start进行排序，避免出现[2,3][3,6][5,9][1,10]这样的情况出现,排序的复杂度为nlogn，比较的复杂度为n

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/**
 * Definition of Interval:
 * public classs Interval {
 *     int start, end;
 *     Interval(int start, int end) {
 *         this.start = start;
 *         this.end = end;
 *     }
 * }
 */
import java.util.*;
public class Solution {
    /**
     * @param intervals: interval list.
     * @return: A new interval list.
     */
 public List<Interval> merge(List<Interval> intervals) {
	        // write your code here
	        	 
	             Collections.sort(intervals, new Comparator<Interval>() {
	                 @Override
	                 public int compare(Interval o1, Interval o2) {
	                     return o1.start - o2.start;
	                 }
	             });

	        
	    for(int i=0;i<intervals.size()-1;i++)
	    {
	        if(intervals.get(i+1).start>intervals.get(i).end)
	    	continue;
	    	if(intervals.get(i+1).end<intervals.get(i).start)
	    	continue;
	    	int newS=Math.min(intervals.get(i).start, intervals.get(i+1).start);
	    	int newE=Math.max(intervals.get(i).end, intervals.get(i+1).end);
	    	Interval temp=new Interval(newS, newE);
	    	intervals.remove(i);
	    	intervals.remove(i);//不能写成i+1
	    	intervals.add(i,temp);
	    	i--;
	    }
	    return intervals;
	    }
	
}

这个写得有点乱

改进了一下，建一个新链表，比较新链表当前位置的end和原链表interval的start大小，看是否要合并区间，把interval插入新链表中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/**
 * Definition of Interval:
 * public classs Interval {
 *     int start, end;
 *     Interval(int start, int end) {
 *         this.start = start;
 *         this.end = end;
 *     }
 * }
 */
import java.util.*;
public class Solution {
    /**
     * @param intervals: interval list.
     * @return: A new interval list.
     */
 	         public List<Interval> merge(List<Interval> intervals) {
	        // write your code here
	        	 List<Interval> res=new ArrayList<Interval>();
	             Collections.sort(intervals, new Comparator<Interval>() {
	                 @Override
	                 public int compare(Interval o1, Interval o2) {
	                     return o1.start - o2.start;
	                 }
	             });
res.add(intervals.get(0));
int cur=0;
	    for(int i=1;i<intervals.size();i++)
	    {
	       
	    	if(intervals.get(i).start>res.get(cur).end)
	    	{res.add(intervals.get(i));
	    	cur+=1;
	    	}
	    	else{
	    	int newE=Math.max(intervals.get(i).end, res.get(cur).end);
            res.get(cur).end=newE;
	    }
	    }
	    return res;
}
}

补充：java List中删除元素

删除 List 中的元素会产生两个问题：

  • 删除元素后 List 的元素数量会发生变化；
  • 对 List 进行删除操作可能会产生并发问题；

List 删除元素的逻辑是将目标元素之后的元素往前移一个索引位置，最后一个元素置为 null，同时 size - 1；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static void main(String[] args) {
    List<Integer> list = new ArrayList<Integer>();
    list.add(1);
    list.add(2);
    list.add(3);
    list.add(3);
    list.add(4);
         
    for (int i=0; i<list.size(); i++) {
        if (list.get(i) == 3) {
            list.remove(i--);
        }
    }
         
    System.out.println(list);
}

建议使用iterator.remove方法

1
2
3
4
5
6
7
8
9
if (null != list && list.size() > 0) {
    Iterator it = list.iterator();  
    while(it.hasNext()){
        Student stu = (Student)it.next(); 
        if (stu.getStudentId() == studentId) {
            it.remove(); //移除该对象
        }
    }
}

参考链接

https://my.oschina.net/xsh1208/blog/504526
https://blog.csdn.net/zzcblogs/article/details/79410002
https://blog.csdn.net/xiaowei132/article/details/48090241
https://blog.csdn.net/claram/article/details/53410175