leetcode2244 如何使用最少的轮数完成任务

蚊子前端博客
发布于 2022-04-24 10:00
如何用最少轮数完成所有的任务

题目链接:2244. 完成所有任务需要的最少轮数。题目的关键点有:

  1. 只能完成相同难度级别的任务;

  2. 每轮只能完成 2 个或 3 个任务;

  3. 使用最少的轮数;

因此我们的思路应当是:统计每个难度级别任务的数量,然后优先 3 个一轮来完成任务,最后剩下的再通过 2 个任务的组合来完成。

只有难度级别的任务的数量为 1 时,无法完成,数量>=1 的,都可以通过 2 和 3 的组合来完成。

优先完成 3 个相同级别的任务,那么最后任务剩余的数量可能是:

  • 0 个:恰好是 3 的倍数;

  • 1 个:还剩下 1 个,但这种情况最后一轮就无法完成了,因此再从前面拿出一个 3,通过 2+2 的方式完成;

  • 2 个:通过完成 2 个相同难度级别的方式完成;

最终实现的 C++代码:

COPYCPP

class Solution { public: int minimumRounds(vector<int> &tasks) { map<int, int> location; // 存储每个级别任务的数量 int leftTaskNum; // 相同级别任务3个一轮全部完成,剩余的任务数量 for (int i = 0, size = tasks.size(); i < size; i++) { auto it = location.find(tasks[i]); if (it == location.end()) { location.insert(pair<int, int>(tasks[i], 1)); } else { it->second += 1; } } map<int, int>::iterator it = location.begin(); int num = 0; while (it != location.end()) { int item = it->second; if (item <= 1) { return -1; } leftTaskNum = item % 3; if (leftTaskNum == 0) { num += item / 3; } else if (leftTaskNum == 1) { num += (item - 3) / 3 + 2; // 从前面拿出3个任务,最后用2+2的方式完成,多加两轮 } else if (leftTaskNum == 2) { num += item / 3 + 1; } it++; } return num; } };
标签:
阅读(260)

公众号:

qrcode

微信公众号:前端小茶馆