贪心算法
这里也有些，建议先看这个
基本概念
所谓贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，它所做出的仅仅是在某种意义上的局部最优解。贪心算法没有固定的算法框架，算法设计的关键是贪心策略的选择。必须注意的是，贪心算法不是对所有问题都能得到整体最优解，选择的贪心策略必须具备无后效性（即某个状态以后的过程不会影响以前的状态，只与当前状态有关。）
模板
求是否走到以及最多需要走多少次。维护end和rightMost。end是上一次的rightMost，每次更新end时要更新次数加1。
class Solution:
def jump(self, nums: List[int]) -> int:
rightmost = 0
end = 0
n = len(nums)
ans = 0
for i in range(n - 1): # 这里为什么是到n-2呢,因为它是当i==end时加一的，所以n-2是最后一个还可以接着跳的点, 也就是可以到最后一个点
rightmost = max(rightmost, i+nums[i])
if i == rightmost:
# 跳不到
return -1
if i == end:
ans += 1
end = rightmost
# 提前返回，其实可以不用
if end >= n - 1:
return ans
return ans
基本例题
case 1：会议室安排
问题描述：设有n个会议的集合C={1,2,…,n}，其中每个会议都要求使用同一个资源（如会议室）而在同一时间内只能有一个会议使用该资源。每个会议i都有要求使用该资源的起始时间bi和结束时间ei，且bi < ei 。如果选择了会议i使用会议室，则它在半开区间[bi, ei)内占用该资源。如果[bi, ei)与[bj , ej)不相交，则称会议i与会议j是相容的。会场安排问题要求在所给的会议集合中选出最大的相容活动子集，也即尽可能地选择更多的会议来使用资源。
求解思路：直观上想，一个会议的结束时间越早，留下给其他会议的时间也就越多，进而可能安排的会议数目也就越多。将各个会议按照结束时间从小到大排序，每次所选择的下一个会议需要满足两个条件：该会议的开始时间大于等于上一个会议的结束时间，且是所满足条件的会议中结束时间最早的那一个。
示例代码
#include <iostream>
#include <algorithm>
using namespace std;
struct Meeting {
int index;
int startTime;
int endTime;
};
bool cmp(Meeting x, Meeting y) {
return x.endTime < y.endTime;
}
void Print(Meeting x) {
cout<<x.index<<" "<<x.startTime<<" "<<x.endTime<<endl;
}
int main() {
int n;
cin>>n;
Meeting meeting[n];
for(int i=0; i<n; i++) {
cin>>meeting[i].index>>meeting[i].startTime>>meeting[i].endTime;
}
sort(meeting,meeting+n,cmp);
cout<<"======会议安排如下========"<<endl;
Print(meeting[0]);
int lastTime = meeting[0].endTime;
for(int i=1; i<n; i++) {
if(meeting[i].startTime >= lastTime) {
Print(meeting[i]);
lastTime = meeting[i].endTime;
}
}
return 0;
}
case 2：分配畜栏
问题描述：农场有N头牛，每头牛会在一个特定的时间区间[A, B]（包括A和B）在畜栏里挤奶，且一个畜栏里同时只能有一头牛在挤奶。现在农场主希望知道最少几个畜栏能满足上述要求，并要求给出每头牛被安排的方案。对于多种可行方案，只输出一种即可。
输入：输入的第一行包含一个整数N(1 ≤ N ≤ 50, 000)，表示有N牛头；接下来N行每行包含两个数，分别表示这头牛的挤奶时间[Ai, Bi](1 ≤ A≤ B ≤ 1, 000, 000)
输出：输出的第一行包含一个整数，表示最少需要的畜栏数；接下来N行，第i+1行描述了第i头牛所被分配的畜栏编号（从1开始）。
解题思路：每头牛都有一个挤奶开始时间和结束时间，当然要优先处理挤奶开始时间早的奶牛。因此首先将所有奶牛按照挤奶开始时间从小到大进行排序，然后按照顺序处理即可，在处理第i头奶牛的时候，首先先查看已经建成的畜栏中是否有空着的（此处可以采用队列，将畜栏按照结束时间从小到大进行排序，队头的畜栏永远是最先结束的，在判断时，只需要判断第一个即可。畜栏的结束时间也就是该畜栏里奶牛挤奶的结束时间），如果有空着的，直接将该头奶牛放进已建成的畜栏即可，如果没有空着的，那么就需要新建一个畜栏，将奶牛放进去挤奶。
示例代码
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
struct Cow {
int a,b; // 挤奶区间的起终点
int No; // 编号
bool operator<(const Cow & c) const {
return a < c.a;
}
} cows[50100];
int pos[50100]; // pos[i]表示编号为i的奶牛去的畜栏编号
struct Stall {
int end; // 结束时间
int No; // 编号
// 重载<，规定了畜栏被排序的规则：结束时间最早的位于队列的最前方
bool operator<(const Stall & s) const {
return end > s.end;
}
Stall(int e, int n):end(e),No(n) { }
};
int main() {
// 读入数据
int n;
scanf("%d", &n);
for(int i=0; i<n; i++) {
scanf("%d%d", &cows[i].a, &cows[i].b);
cows[i].No = i;
}
sort(cows,cows+n); // 对奶牛按照开始挤奶的时间从小到大排序
int total = 0; // 记录总共分配了多少畜栏
priority_queue<Stall> pq; // 优先队列，用来存放畜栏，按照结束时间从小到大排序
for(int i=0; i<n; i++) {
if(pq.empty()) {
total ++;
pq.push(Stall(cows[i].b, total));
pos[cows[i].No] = total;
} else {
Stall st = pq.top();
if(st.end < cows[i].a) {
pq.pop();
pos[cows[i].No] = st.No;
pq.push(Stall(cows[i].b,st.No));
} else {
total ++;
pq.push(Stall{cows[i].b, total});
pos[cows[i].No] = total;
}
}
}
cout<<"供分配了 "<<total <<" 个畜栏"<<endl;
for(int i=0; i<n; i++) {
cout<<"奶牛编号: "<<cows[i].No+1<<" 畜栏编号: "<<pos[i]<<endl;
}
return 0;
}
case 3：放置雷达
问题描述：x轴是海岸线，x轴上方是海洋。海洋中有n个岛屿，可以看作点。给定每个岛屿的坐标(x,y)，x,y都是整数。当一个雷达（可看作点）到岛屿的距离不超过d（整数），则认为该雷达覆盖了该岛屿。雷达只能放置在x轴上。问至少需要多少个雷达才可以覆盖全部岛屿。
求解思路：原问题比较复杂，首先我们将问题进行一个转化：对于每个岛屿，可以计算出，覆盖它的雷达，必须位于x轴上的区间[Ps,Pe]。如下图所示：
如果有雷达位于某个x轴区间[a,b]，称该雷达覆盖此区间。问题转化为，至少要在x轴上放置几个雷达（点），才能覆盖全部区间。
- 重要结论：如果可以找到一个雷达同时覆盖多个区间，那么把这多个区间按照起点坐标从小到大排序，则最后一个区间（起点最靠右）
k的起点，就能覆盖所有区间。因此，我们就可以只挑区间的起点来放置雷达了。 - 首先将所有区间按照从小到大排序，并编号
0~n-1。依次考察每个区间的起点，看要不要在那里放置雷达。开始，所有的区间都没有被覆盖，定义一个变量firstNoConvered指向编号最小的且未被覆盖的区间编号，因此最初始状态firstNoConvered=0。接着我们依次遍历起点，在第0个区间起点可放置的情况下，先不着急放置雷达，再看放置第1个区间起点是否可以覆盖前面的0区间，如果可以继续往下看第2个区间的起点，看放置在该点是否可以覆盖前面的0,1号区间，如果不可以的话，就将第一个雷达放置在1号区间的起点，然后firstNoConvered=2指向第二个区间；如果可以的话继续按照该思路往下看
输入与输出：输入有两部分构成。第一行输入m和r，m代表海上岛屿的数量,r代表雷达的覆盖半径。接下来的m行分别表示各个雷达的坐标(x,y)。输出放置最小数量的雷达数目即可。
示例代码
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
int R = 2;
struct Point {
int x;
int y;
};
struct QuJian {
int No;
int left;
int right;
bool operator<(const QuJian & qujian) const {
return left < qujian.left;
}
};
int main() {
// 输入数据
int m,r;
cin>>m>>r;
Point point[m];
for(int i=0; i<m; i++) {
cin>>point[i].x>>point[i].y;
}
// 转化为区间
QuJian qj[m];
for(int i=0; i<m; i++) {
qj[i].left = point[i].x - sqrt(R*R-point[i].y*point[i].y);
qj[i].right = point[i].x + sqrt(R*R-point[i].y*point[i].y);
}
// 区间按照左端点从小到大排序
sort(qj,qj+m);
int total = 0;
for(int i=0; i<m; i++) {
if(i == m-1) {
cout<<"最少放置雷达数: "<<total+1<<endl;
return 0;
}
int minRight = qj[i].right;
for(int j=i+1; j<m; j++) {
if(qj[j].left <= minRight) {
minRight = min(minRight,qj[j].right);
if(j == m-1) {
cout<<"最少放置雷达数: "<<total+1<<endl;
return 0;
}
} else {
total ++; // 放置雷达在编号为j-1的区间起点
i = j;
i--; // break之后i还要+1，所以要先-1，才能将j的值赋给i
break;
}
}
}
return 0;
}
必看
覆盖游戏
class Solution:
def canJump(self, nums: List[int]) -> bool:
n, rightmost = len(nums), 0
for i in range(n):
if i <= rightmost:
rightmost = max(rightmost, i + nums[i])
if rightmost >= n - 1:
return True
return False
class Solution:
def jump(self, nums: List[int]) -> int:
rightmost = 0
end = 0
n = len(nums)
ans = 0
for i in range(n - 1): # 这里为什么是到n-2呢,因为它是当i==end时加一的，所以n-2是最后一个还可以接着跳的点, 也就是可以到最后一个点
rightmost = max(rightmost, i+nums[i])
if i == rightmost:
# 跳不到
return -1
if i == end:
ans += 1
end = rightmost
# 提前返回，其实可以不用
if end >= n - 1:
return ans
return ans
class Solution:
def videoStitching(self, clips: List[List[int]], T: int) -> int:
furthest = [0] * (T + 1)
for s, e in clips:
for i in range(s, min(T, e) + 1):
furthest[i] = max(furthest[i], e)
rightmost = 0
end = 0
ans = 0
for i in range(T):
rightmost = max(furthest[i], rightmost)
if i == rightmost:
return -1
if i == end:
ans += 1
end = rightmost
return ans
class Solution:
def minTaps(self, n: int, ranges: List[int]) -> int:
garden = [0 for _ in range(n + 1)]
for i, v in enumerate(ranges):
s, e = i - v, i + v
s = max(0, s)
e = min(n, e)
for j in range(s, e + 1):
garden[j] = max(garden[j], e)
ans = end = rightmost = 0
for i in range(n):
rightmost = max(rightmost, garden[i])
if i == rightmost:
return -1
if i == end:
ans += 1
end = rightmost
return ans
class Solution:
def minTaps(self, n: int, ranges: List[int]) -> int:
garden = [0 for _ in range(n + 1)]
for i, v in enumerate(ranges):
s, e = i - v, i + v
s = max(0, s)
e = min(n, e)
for j in range(s, e + 1):
garden[j] = max(garden[j], e)
inf = float('inf')
dp = [inf for _ in range(n + 1)]
# dp[i] = min(dp[i], dp[j] + 1) for garden[i] = j
dp[n] = 0
for i in range(n, -1, -1):
j = garden[i]
dp[i] = min(dp[i], dp[j] + 1)
if dp[i] == inf:
return -1
return dp[0]