b_lc_完成任务的最少工作时间段（贪心(×) / 枚举）
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了b_lc_完成任务的最少工作时间段（贪心(×) / 枚举），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1560字，纯文字阅读大概需要3分钟。
内容图文
第 i 个任务需要花费 tasks[i] 小时完成。一个 工作时间段 中，你可以 至多 连续工作 sessionTime 个小时，然后休息一会儿。
你需要按照如下条件完成给定任务：
- 如果你在某一个时间段开始一个任务，你需要在 同一个 时间段完成它。
- 完成一个任务后，你可以 立马 开始一个新的任务。
- 你可以按 任意顺序 完成任务。
给你 tasks 和 sessionTime ，请你按照上述要求，返回完成所有任务所需要的 最少 数目的 工作时间段 。
思路：一开始一维可以用贪心做，但是发现有特殊样例没过掉，
class Solution {
public:
int minSessions(vector<int>& A, int sessionTime) {
int n = A.size();
multiset<int> st;
for (int i = 0; i < n; ++i) {
st.insert(sessionTime);
}
sort(A.begin(), A.end());
int ans = 0;
for (int i = n - 1; i >= 0; --i) {
int a = A[i];
auto it = st.lower_bound(a);
if (*it == sessionTime) {
ans++;
}
int r = *it - a;
st.erase(it);
if (r != 0) {
st.insert(r);
}
}
return ans;
}
};
递归枚举状态：对于每个任务来说，要么新开一个 session 去做、要么在已经开了的 session 去执行，为了实现存储，需要容器去存储以前开启了的 session：
class Solution {
public:
int ans = INT_MAX;
void dfs(int i, int sessionTime, vector<int> curSessions, vector<int>& A) {
if (curSessions.size() >= ans) {
return;
}
if (i >= A.size()) {
ans = min(ans, (int) curSessions.size());
return;
}
//在原有的session上做任务
for (int j = 0; j < curSessions.size(); ++j) {
if (A[i] + curSessions[j] <= sessionTime) {
curSessions[j] += A[i];
dfs(i + 1, sessionTime, curSessions, A);
curSessions[j] -= A[i];
}
}
//新开session
curSessions.push_back(A[i]);
dfs(i + 1, sessionTime, curSessions, A);
curSessions.pop_back();
}
int minSessions(vector<int>& A, int sessionTime) {
vector<int> curSessions;
dfs(0, sessionTime, curSessions, A);
return ans;
}
};
原文：https://www.cnblogs.com/wdt1/p/15202287.html
内容总结
以上是互联网集市为您收集整理的b_lc_完成任务的最少工作时间段（贪心(×) / 枚举）全部内容，希望文章能够帮你解决b_lc_完成任务的最少工作时间段（贪心(×) / 枚举）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。