当前位置:网站首页>LeetCode 1986. The minimum working time to complete the task is one question per day
LeetCode 1986. The minimum working time to complete the task is one question per day
2022-07-07 16:59:00 【@Little safflower】
Problem description
You are arranged n A mission . The duration of the task is n Array of integers for tasks Express , The first i Tasks cost tasks[i] Hours to complete . One Working hours in , You can at most Continuous work sessionTime Hours , Then take a rest .
You need to complete the given task according to the following conditions :
If you start a task at a certain time , You need to The same Time period to complete it .
After completing a task , You can Immediately Start a new task .
You can press In any order To complete the task .
Here you are. tasks and sessionTime , Please follow the above requirements , Return to what is needed to complete all tasks least Count Working hours .Test data guarantee sessionTime Greater than or equal to tasks[i] Medium Maximum .
Example 1:
Input :tasks = [1,2,3], sessionTime = 3
Output :2
explain : You can complete all tasks in two working hours .
- The first working period : Complete the first and second tasks , cost 1 + 2 = 3 Hours .
- The second working period : Complete the third task , cost 3 Hours .
Example 2:Input :tasks = [3,1,3,1,1], sessionTime = 8
Output :2
explain : You can complete all tasks in two working hours .
- The first working period : Complete all tasks except the last one , cost 3 + 1 + 3 + 1 = 8 Hours .
- The second working period , Finish the last task , cost 1 Hours .
Example 3:Input :tasks = [1,2,3,4,5], sessionTime = 15
Output :1
explain : You can complete all tasks in one working time .
Tips :
n == tasks.length
1 <= n <= 14
1 <= tasks[i] <= 10
max(tasks[i]) <= sessionTime <= 15source : Power button (LeetCode)
link :https://leetcode.cn/problems/minimum-number-of-work-sessions-to-finish-the-tasks
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .
Java
class Solution {
public int minSessions(int[] tasks, int sessionTime) {
Arrays.sort(tasks);
int n = tasks.length;
int left = 1;
int right = n;
while(left < right){
int mid = (left + right) >> 1;
int[] timeParagraph = new int[mid];
if(dfs(n - 1,tasks,timeParagraph,mid,sessionTime)){
right = mid;
}else {
left = mid + 1;
}
}
return left;
}
public boolean dfs(int index,int[] tasks,int[] timeParagraph,int mid,int sessionTime){
if(index == -1) return true;
boolean[] visible = new boolean[sessionTime + 1];
// Traverse every time segment
for(int i = 0;i < mid;i++){
// If the value of the previous bucket has already appeared , You can skip the bucket , Try to put into the next bucket
if(visible[timeParagraph[i]]) continue;
visible[timeParagraph[i]] = true;
int t = timeParagraph[i] + tasks[index];
if(t <= sessionTime){
timeParagraph[i] = t;
if(dfs(index - 1,tasks,timeParagraph,mid,sessionTime)) return true;
timeParagraph[i] -= tasks[index];
}
}
return false;
}
}
边栏推荐
- Cesium (4): the reason why gltf model is very dark after loading
- LeetCode 1477. 找两个和为目标值且不重叠的子数组 每日一题
- Introduction and use of gateway
- LocalStorage和SessionStorage
- Pycharm IDE下载
- ATM system
- Sort out several important Android knowledge and advanced Android development interview questions
- Build an all in one application development platform, light flow, and establish a code free industry benchmark
- Binary search tree (basic operation)
- dapp丨defi丨nft丨lp单双币流动性挖矿系统开发详细说明及源码
猜你喜欢
Spark Tuning (III): persistence reduces secondary queries
The team of East China Normal University proposed the systematic molecular implementation of convolutional neural network with DNA regulation circuit
二叉搜索树(特性篇)
3000 words speak through HTTP cache
最新2022年Android大厂面试经验,安卓View+Handler+Binder
值得一看,面试考点与面试技巧
Pycharm IDE下载
Prediction - Grey Prediction
Seaborn数据可视化
[C language] question set of X
随机推荐
LeetCode 300. 最长递增子序列 每日一题
Interface oriented programming
LeetCode 1986. 完成任务的最少工作时间段 每日一题
【Seaborn】组合图表:PairPlot和JointPlot
[designmode] facade patterns
蓝桥杯 决赛 异或变换 100分
LocalStorage和SessionStorage
LeetCode 1774. 最接近目标价格的甜点成本 每日一题
As an Android Developer programmer, Android advanced interview
QT 图片背景色像素处理法
[designmode] proxy pattern
模块六
Seaborn数据可视化
面向接口编程
LeetCode 152. 乘积最大子数组 每日一题
Localstorage and sessionstorage
全网“追杀”钟薛高
Vs2019 configuration matrix library eigen
一文读懂数仓中的pg_stat
作为Android开发程序员,android高级面试