IVN
0%

区间问题

Posted on Edited on In
Symbols count in article: 8.1k Reading time ≈ 7 mins.

区间问题选编

maximum number of non-overlapping intervals:

  1. 按interval的end升序排序
  2. 选中集合中end最小的interval
  3. 删去所有与该interval重叠的interval(s)
  4. 重复2、3, 直到集合为空
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        int n=intervals.length;
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[1]-o2[1];
            }
        });
        int count=1;
        int end=intervals[0][1];
        for (int[] interval : intervals) {
            int start=interval[0];
            if(start>=end){
                count++;
                end=interval[1];
            }
        }
        return n-count;
    }
}

1288. Remove Covered Intervals

start升序、end降序

对于两个起点相同的区间，需要保证长的那个区间在上面（按照终点降序），这样才会被判定为覆盖，否则会被错误地判定为相交，少算一个覆盖区间。

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
public class LeetCode1288 {
    public int removeCoveredIntervals(int[][] intervals) {
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0]!=o2[0] ? o1[0]-o2[0] : o2[1]-o1[1];
            }
        });
        int start=intervals[0][0];
        int end=intervals[0][1];
        int count=-1;
        int n=intervals.length;
        for (int[] interval : intervals) {
            int left=interval[0];
            int right=interval[1];
            if(right<=end){
                count++;
            }else if(left<end){
                end=right;
            }else{
                start=left;
                end=right;
            }
        }
        return n-count;
    }
}

56. Merge Intervals

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
public class LeetCode56 {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0]!=o2[0] ? o1[0]-o2[0] : o2[1]-o1[1];
            }
        });
        List<int[]> res=new ArrayList<>();
        int start=intervals[0][0];
        int end=intervals[0][1];
        for (int i = 1; i < intervals.length; i++) {
            int left=intervals[i][0];
            int right=intervals[i][1];
            if(right<=end){//contains
                continue;
            }else if(left<=end){//overlap
                end=right;
            }else{//non-overlapping
                res.add(new int[]{start,end});
                start=left;
                end=right;
            }
        }
        res.add(new int[]{start,end});
        int[][] array=new int[res.size()][2];
        for (int i = 0; i < array.length; i++) {
            array[i][0]=res.get(i)[0];
            array[i][1]=res.get(i)[1];
        }
        return array;
    }
}

986. Interval List Intersections

两个区间集合已升序

找交集：双指针i , j

  • a1, a2, b1, b2
  • 无交集：
  • 有交集：
  • 无论有无交集，指针都要后移：
  • 一旦某一集合遍历完毕，则退出
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
public class LeetCode986 {
    public int[][] intervalIntersection(int[][] firstList, int[][] secondList) {
        int n1=firstList.length;
        int n2=secondList.length;
        int i=0;
        int j=0;
        List<int[]> list=new ArrayList<>();
        while(i<n1 && j<n2){
            int a1=firstList[i][0];
            int a2=firstList[i][1];
            int b1=secondList[j][0];
            int b2=secondList[j][1];
            if(b1<=a2 && a1<=b2){
                int c1=Math.max(a1,b1);
                int c2=Math.min(a2,b2);
                list.add(new int[]{c1,c2});
            }
            if(a2<b2){
                i++;
            }else{
                j++;
            }
        }
        int[][] res=new int[list.size()][2];
        for (i = 0; i < res.length; i++) {
            res[i][0]=list.get(i)[0];
            res[i][1]=list.get(i)[1];
        }
        return res;
    }
}

452. Minimum Number of Arrows to Burst Balloons

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
public int findMinArrowShots(int[][] points) {
    //[[-2147483646,-2147483645],[2147483646,2147483647]]
    //Arrays.sort(points,(a,b)->(a[1]-b[1]));
    Arrays.sort(points, new Comparator<int[]>() {
        @Override
        public int compare(int[] o1, int[] o2) {
            if(o1[1]<=o2[1]){
                return -1;
            }else{
                return 1;
            }
        }
    });
    int n=points.length;
    int res=1;
    int start=points[0][0];
    int end=points[0][1];
    for (int i = 2; i < n; i++) {
        int left=points[i][0];
        int right=points[i][1];
        if(left>end){
            start=left;
            end=right;
            res++;
        }
    }
    return res;
}

646. Maximum Length of Pair Chain

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int findLongestChain(int[][] pairs) {
    Arrays.sort(pairs,(a,b)->(a[1]-b[1]));
    //2,5   1,5    6,8
    int n=pairs.length;
    int end=pairs[0][1];
    int res=1;
    int cur=1;
    for (int i = 1; i < n; i++) {
        int[] pair=pairs[i];
        if(end<pair[0]){
            end=pair[1];
            cur++;
            res=Math.max(res,cur);
        }
    }
    return res;
}

218. The Skyline Problem

不愧是hard题！

注意：

  1. SortedSet去重，同一x坐标只保留一根
  2. 根据每个building，更新每个x坐标的最大高度
  3. 遍历，当最大高度改变时，则更新res
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
public List<List<Integer>> getSkyline(int[][] buildings) {
    SortedSet<Integer> set=new TreeSet<>();
    for (int[] building : buildings) {
        int left=building[0];
        int right=building[1];
        set.add(left);
        set.add(right);
    }
    List<Integer> edges=new ArrayList<>(set);
    Map<Integer,Integer> map=new HashMap<>();
    for (int i = 0; i < edges.size(); i++) {
        map.put(edges.get(i),i);
    }
    int[] heights=new int[edges.size()];
    for (int[] building : buildings) {
        int left=building[0];
        int right=building[1];
        int height=building[2];
        int iLeft=map.get(left);
        int iRight=map.get(right);
        for(int i=iLeft; i<iRight; i++){
            heights[i]=Math.max(heights[i],height);
        }
    }
    List<List<Integer>> res=new ArrayList<>();
    for (int i = 0; i < heights.length; i++) {
        int cur=edges.get(i);
        int curHeight=heights[i];
        if(res.isEmpty() || res.get(res.size()-1).get(1)!=curHeight){
            res.add(new ArrayList<>(Arrays.asList(cur,curHeight)));
        }
    }
    return res;
}

759. Employee Free Time

start升序、end降序

对于两个起点相同的区间，需要保证长的那个区间在上面（按照终点降序），这样才会被判定为覆盖，否则会被错误地判定为相交，少算一个覆盖区间。

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
46
47
48
49
50
51
52
53
public class LeetCode759 {
    class Interval {
        public int start;
        public int end;

        public Interval() {}

        public Interval(int _start, int _end) {
            start = _start;
            end = _end;
        }
    };
    public List<Interval> employeeFreeTime(List<List<Interval>> schedule) {
        //merge intervals
        List<Interval> list=new ArrayList<>();
        for (List<Interval> intervals : schedule) {
            for (Interval interval : intervals) {
                list.add(interval);
            }
        }
        //start ascending, end descending
        Collections.sort(list,(a,b)->(a.start!=b.start ? a.start-b.start : b.end-a.end));
        //[1,5], [2,5], [1,6]
        List<int[]> work=new ArrayList<>();
        int left=list.get(0).start;
        int right=list.get(0).end;
        for (int i = 1; i < list.size(); i++) {
            Interval cur=list.get(i);
            int start=cur.start;
            int end=cur.end;
            if(start<=right){
                right=Math.max(right,end);
            }else{
                //start>right
                //[left,right] [start,end]
                work.add(new int[]{left,right});
                left=start;
                right=end;
            }
        }
        work.add(new int[]{left,right});
        List<Interval> res=new ArrayList<>();
        int start=work.get(0)[1];
        for (int i = 1; i < work.size(); i++) {
            int[] cur=work.get(i);
            res.add(new Interval(start,cur[0]));
            start=cur[1];
        }
        return res;
    }


}

1229. Meeting Scheduler

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public List<Integer> minAvailableDuration(int[][] slots1, int[][] slots2, int duration) {
    Arrays.sort(slots1,(a,b)->(a[0]-b[0]));
    Arrays.sort(slots2,(a,b)->(a[0]-b[0]));
    List<Integer> res=new ArrayList<>();
    f:for (int[] arr1 : slots1) {
        for (int[] arr2 : slots2) {
            if(arr1[0]>=arr2[1]){
                continue;
            }
            if(arr1[1]<=arr2[0]){
                break;
            }
            int a=Math.max(arr1[0],arr2[0]);
            int b=Math.min(arr1[1],arr2[1]);
            if(b-a>=duration){
                res.add(a);
                res.add(a+duration);
                break f;
            }
        }
    }
    return res;
}

1272. Remove 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
public List<List<Integer>> removeInterval(int[][] intervals, int[] toBeRemoved) {
    List<List<Integer>> res=new LinkedList<>();
    int left=toBeRemoved[0];
    int right=toBeRemoved[1];
    //[left,right)
    for (int[] interval : intervals) {
        //[start,end)
        int start=interval[0];
        int end=interval[1];
        //no overlap
        if(start>=right || end<=left){
            res.add(new LinkedList<>(Arrays.asList(start,end)));
            continue;
        }
        //has overlap
        if(start<left){
            res.add(new LinkedList<>(Arrays.asList(start,left)));
        }
        if(end>right){
            res.add(new LinkedList<>(Arrays.asList(right,end)));
        }
    }
    return res;
}

435. Non-overlapping Intervals

区间问题：

  1. non-overlapping intervals: end升序
  2. covered intervals: start升序, end降序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int eraseOverlapIntervals(int[][] intervals) {
    int count=0;
    Arrays.sort(intervals,(a,b)->(a[1]-b[1]));
    int right=intervals[0][1];
    int n=intervals.length;
    for (int i = 1; i < n; i++) {
        if(intervals[i][0]<right){
            count++;
        }else{
            right=intervals[i][1];
        }
    }
    return count;
}