240. Search a 2D Matrix II
Write an efficient algorithm that searches for a value target in an m x n integer matrix matrix. This matrix has the following properties:
- Integers in each row are sorted in ascending from left to right.
- Integers in each column are sorted in ascending from top to bottom.
Example 1:
Input: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
Output: trueExample 2:
Input: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20
Output: false解题思路
- 暴力遍历法
```c++
class Solution {
public:
bool searchMatrix(vector<vector
2. **二分查找**
```c++
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
for (const auto& row: matrix) {
auto it = lower_bound(row.begin(), row.end(), target);
if (it != row.end() && *it == target) {
return true;
}
}
return false;
}
};
关于low_bound函数，参见文档
3.Z字形查找
```c++
class Solution {
public:
bool searchMatrix(vector<vector
# 435. Non-overlapping Intervals
Given an array of intervals `intervals` where `intervals[i] = [starti, endi]`, return *the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping*.
<a href="">link</a>
**Example 1:**
Input: intervals = [[1,2],[2,3],[3,4],[1,3]] Output: 1 Explanation: [1,3] can be removed and the rest of the intervals are non-overlapping.
**Example 2:**
Input: intervals = [[1,2],[1,2],[1,2]] Output: 2 Explanation: You need to remove two [1,2] to make the rest of the intervals non-overlapping.
**Example 3:**
Input: intervals = [[1,2],[2,3]] Output: 0 Explanation: You don't need to remove any of the intervals since they're already non-overlapping.
## 解题思路
1.**动态规划**
题目的要求等价于「选出最多数量的区间，使得它们互不重叠」。由于选出的区间互不重叠，因此我们可以将它们按照端点从小到大的顺序进行排序，并且无论我们按照左端点还是右端点进行排序，得到的结果都是唯一的。
这样一来，我们可以先将所有的 n 个区间按照左端点（或者右端点）从小到大进行排序，随后使用动态规划的方法求出区间数量的最大值。设排完序后这 n 个区间的左右端点分别为 $l_0,⋯ ,l_{n−1} $以及$ r_0,⋯ ,r_{n−1}$，那么我们令 $f_i$表示「以区间 i 为最后一个区间，可以选出的区间数量的最大值」，状态转移方程即为：
$$f_i=\displaystyle{max_{j<i ∧ rj≤li}}{fj}+1$$
即我们枚举倒数第二个区间的编号 j，满足 j<i，并且第 j个区间必须要与第 i 个区间不重叠。由于我们已经按照左端点进行升序排序了，因此只要第 j 个区间的右端点 $r_j $没有越过第 i 个区间的左端点 $l_i$，即 $r_j \leq l_i$，那么第 jjj 个区间就与第 i 个区间不重叠。我们在所有满足要求的 j 中，选择 $f_j$ 最大的那一个进行状态转移，如果找不到满足要求的区间，那么状态转移方程中 max这一项就为 0，$f_i$ 就为 1。
最终的答案即为所有 $f_i $中的最大值。
```c++
class Solution {
public:
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
if (intervals.empty()) {
return 0;
}
sort(intervals.begin(), intervals.end(), [](const auto& u, const auto& v) {
return u[0] < v[0];
});
int n = intervals.size();
vector<int> f(n, 1);
for (int i = 1; i < n; ++i) {
for (int j = 0; j < i; ++j) {
if (intervals[j][1] <= intervals[i][0]) {
f[i] = max(f[i], f[j] + 1);
}
}
}
return n - *max_element(f.begin(), f.end());
}
};
2.贪心算法
关于为什么是按照区间右端点排序？
官解里对这个描述的非常清楚了，这个题其实是预定会议的一个问题，给你若干时间的会议，然后去预定会议，那么能够预定的最大的会议数量是多少？核心在于我们要找到最大不重叠区间的个数。 如果我们把本题的区间看成是会议，那么按照右端点排序，我们一定能够找到一个最先结束的会议，而这个会议一定是我们需要添加到最终结果的的首个会议。（这个不难贪心得到，因为这样能够给后面预留的时间更长）。
关于为什么是不能按照区间左端点排序？
这里补充一下为什么不能按照区间左端点排序。同样地，我们把本题的区间看成是会议，如果“按照左端点排序，我们一定能够找到一个最先开始的会议”，但是最先开始的会议，不一定最先结束。。举个例子：
|_________| 区间a
|___| 区间b
|__| 区间c
|______| 区间d 区间a是最先开始的，如果我们采用区间a作为放入最大不重叠区间的首个区间，那么后面我们只能采用区间d作为第二个放入最大不重叠区间的区间，但这样的话，最大不重叠区间的数量为2。但是如果我们采用区间b作为放入最大不重叠区间的首个区间，那么最大不重叠区间的数量为3，因为区间b是最先结束的。
```c++
class Solution {
public:
int eraseOverlapIntervals(vector<vector
sort(intervals.begin(), intervals.end(), [](const auto& u, const auto& v) {
return u[1] < v[1];
});
int n = intervals.size();
int right = intervals[0][1];
int ans = 1;
for (int i = 1; i < n; ++i) {
if (intervals[i][0] >= right) {
++ans;
right = intervals[i][1];
}
}
return n - ans;
}};