题目链接

员工分组

题目描述

给定一个员工数组 staff，其中0表示新员工，1表示老员工。需要按照以下规则对员工进行分组，并求出所需的最小分组数：

  1. 一个小组至多3个员工。
  2. 一个小组中最多有1个老员工。
  3. 如果一个小组中有1个老员工，那么这组最多有2个员工。

思路分析

这是一个典型的贪心问题。为了使分组数最少，我们应该在满足所有规则的前提下，让每个小组容纳尽可能多的员工。

首先，我们可以统计出老员工（值为1）和新员工（值为0）的各自数量，分别设为 num_old 和 num_new。

分析分组规则可以发现，老员工是分组的主要限制因素：

  • 每个老员工都必须占用一个独立的小组，因为一个小组最多只能有1名老员工。因此，我们至少需要 num_old 个小组。
  • 包含老员工的小组，总人数不能超过2人。这意味着每个老员工最多只能带1名新员工。

基于此，我们可以制定如下贪心策略：

  1. 优先处理老员工：为 num_old 个老员工每人建立一个小组。这部分就确定了 num_old 个小组。

  2. 老员工带新员工：为了尽可能地消化员工，我们让每个老员工的小组都尝试容纳一名新员工。这 num_old 个小组总共可以带 num_old 名新员工。

  3. 处理剩余的新员工：

    • 与老员工配对后，还剩下的新员工数量为 remaining_new = max(0, num_new - num_old)。
    • 这些剩下的新员工只能自己组队。对于纯新员工的小组，规则1（一个小组至多3个员工）适用。
    • 为了最小化分组数，我们应该将这些剩余的新员工按3人一组进行打包。所需的小组数为 。在整数运算中，这等价于 (remaining_new + 2) / 3。

最终，总的最小分组数就是老员工形成的小组数与剩余新员工形成的小组数之和。

代码

#include <vector>
#include <numeric>
#include <algorithm>

using namespace std;

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param staff int整型vector 
     * @return int整型
     */
    int staffGroup(vector<int>& staff) {
        int num_new = 0;
        int num_old = 0;
        for (int s : staff) {
            if (s == 0) {
                num_new++;
            } else {
                num_old++;
            }
        }

        int remaining_new = max(0, num_new - num_old);
        int groups_for_new = (remaining_new + 2) / 3;
        
        return num_old + groups_for_new;
    }
};

class Solution {
    public int staffGroup(int[] staff) {
        int num_new = 0;
        int num_old = 0;
        for (int s : staff) {
            if (s == 0) {
                num_new++;
            } else {
                num_old++;
            }
        }

        int remaining_new = Math.max(0, num_new - num_old);
        int groups_for_new = (remaining_new + 2) / 3;

        return num_old + groups_for_new;
    }
}

class Solution:
    def staffGroup(self, staff):
        num_new = staff.count(0)
        num_old = staff.count(1)

        remaining_new = max(0, num_new - num_old)
        # 向上取整的整数除法
        groups_for_new = (remaining_new + 2) // 3
        
        return num_old + groups_for_new

算法及复杂度

  • 算法：贪心
  • 时间复杂度：，其中 是员工总数。我们只需要遍历一次数组来统计新老员工的数量。
  • 空间复杂度：，我们只需要常数个变量来存储计数。