b_lc_完成任务的最少工作时间段(贪心(×) / 枚举)

第 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;
    }
};
上一篇:【数据结构与算法】有序线性表的有序合并


下一篇:LC 计数质数