【vivo秋招0912】三、最少开发工时总和 ＜模拟＞

三、最少开发工时总和

某开发小组近期承接了多个研发项目，作为组长的你需要为员工分配工作任务。具体要求如下:
项目划分到的任务工时用二维数组 tasks 表示，其中 tasks[i][j] 表示的是第 i 个项目中第 j 个任务的开发工时；现在组内员工有 n 个，每个工作任务只能分配给一位员工，一位员工可以被分配多个任务，一个任务完成才能进行下一个任务，且每个项目必须所有员工参与。
请为组内员工设计一套最合理的工作任务安排，使得每个项目中各员工的工作时长最接近，计算并返回每个项目中员工最少的开发工时总和。

注意:
1 <= n <= tasks[i].length <= 10
1 <= tasks[i][j] <= 30

示例输入：

[[2,3,1],[1,2,6,2],[3,2]],2
1

输出：

10
1

解释：

总共2个员工
第1个项目[2,3,1]，分给2个员工为[3],[2,1]，最少的为 [3] 或 [2,1]
第2个项目[1,2,6,2]，分给2个员工为[1,2,2],[6]，最少的为[1,2,2]
第3个项目[3,2]，分给2个员工为[3],[2]，最少的为[2]
所有项目最少工作时长总和: 3+5+2=10
1
2
3
4
5

题解

思路：分配每个项目中任务，均匀分配为 n 份，取均匀分配完最小的那份。然后累加。

	public int leastTimeSum (int[][] tasks, int n) {
	    int allCost = 0;
	
	    for(int[] mission: tasks){
	        int length = mission.length;
	        
	        // 分不了n份，说明最小那份是0
	        if(length<n){
	            continue;
	        }
	        Arrays.sort(mission);
	        
	        //对于每一个任务构造 n个槽，并且都是0
	        int[] nowCost = new int[n];
	        for(int i=0;i<n;i++){
	            nowCost[i]=0;
	        }
	        
	        for(int i =length-1;i>=0;i--){
	            //找槽总数最小的那个下标
	            int index = minIndex(nowCost);
	            //放进槽小的那个
	            nowCost[index] += mission[i];
	        }
	
	        // 加上槽最少的那组
	        allCost += nowCost[minIndex(nowCost)];
	
	    }
	    return allCost;
	}
	
	// 第几个槽 总数最小
	public static int minIndex(int[] array){
	    int min =array[0];
	    int index = 0;
	    for(int i =0;i<array.length;i++){
	        if(array[i]<min){
	            min = array[i];
	            index = i;
	        }
	    }
	    return index;
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44