将交叉口大小设置为至少两个-数据结构与算法(中)

当前位置:　首页>> 技术小册>> 数据结构与算法(中)

难度:
Hard

题意：

1. 给定n个区间
2. 求一个最小集合，使得每个区间，集合中至少有两个数在区间里面

思路：

- 这题是贪心题
- 先对区间右端点排序。再从右端点小的开始贪心。每次先判断当前集合中是否有两个数在这个区间中，如果有，直接跳过，没有，从右端点开始往集合丢数，直到有两个数在这个区间中
- 直观的解释就是，为了满足前面的区间的条件，而丢进集合的数一定是越大越好，这样跟后面的区间共用一个数的几率会更大

解法：

```java
class Solution {
	 public int intersectionSizeTwo(int[][] intervals) {
        Integer[] array = new Integer[intervals.length];
        for (int i = 0;i < array.length;i++) {
            array[i] = i;
        }
        Arrays.sort(array, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return Integer.compare(intervals[o1][1], intervals[o2][1]);
            }
        });
        List<Integer> result = new ArrayList<Integer>();
        int[] t = new int[2];
        for (int i = 0;i < array.length;i++) {
            int n = 0;
            if (result.size() > 0 && result.get(result.size() - 1) >= intervals[array[i]][0]) {
                t[n++] = result.get(result.size() - 1);
            }
            if (result.size() > 1 && result.get(result.size() - 2) >= intervals[array[i]][0]) {
                t[n++] = result.get(result.size() - 2);
            }
            int res = n;
            int j = intervals[array[i]][1];
            while (n != 2) {
                boolean found = false;
                for (int k = 0;k < n;k++) {
                    if (t[k] == j) {
                        found = true;
                        break;
                    }
                }
                if (found) {
                    j--;
                } else {
                    t[n++] = j--;
                }
            }
            if (res == 0) {
                result.add(t[1]);
                result.add(t[0]);
            }
            if (res == 1) {
                result.add(t[1]);
            }
        }
        return result.size();
    }
}
```

该分类下的相关小册推荐：

编程之道-算法面试(上)

数据结构与算法(上)

算法面试通关 50 讲

数据结构与算法(下)

业务开发实用算法精讲

数据结构与算法之美

编程之道-算法面试(下)