一个小小的算法题，感兴趣的话请分享一下解法
本帖最后由 pansong291 于 2021-12-1 20:45 编辑小明写了一个程序，这个程序可以按照设定，在指定时间段内持续运行或者在指定时间段内不运行。
可以设定的参数如下：
1. 总运行次数
2. 每天运行的时间段（比如 9 点到 18 点，如果反过来， 18 点到 9 点，则是跨天的时间段）
3. 可运行周期（这个周期是礼拜设置，比如 周一 周二 周五 周日，那么在这些天里是会运行的，其他则不会运行）
4. 开始日期和结束日期（比如 2021年11月1号到 2021年11月10号）
现在小明想知道，按照以上这样的固定设置，指定日期范围内是否全部都符合规定，以及符合规定的天数最多有多少天。
需要注意的是，指定时间内运行是符合规定的，指定时间内不运行也是符合规定的哦。如果指定时间内需要运行却没有运行，或指定时间内不运行却运行了则是不符合规定的。
如果还是无法理解题意，可以将下面代码载入浏览器运行查看效果。
我的思路大致如下：
先获取连续的日期子区间，再分别将各个子区间的运行次数相加。而各个子区间是连续的，若不跨天则运行次数等于天数，若跨天，再加一即可。
如下图，若日期范围为 1 号到 10 号，周期为周一、周二、周五、周日，那么计算出至少需要的运行次数应为 9 次（图中蓝色块个数），其中有 6 天是运行的，4 天是不运行的，符合规定的最多天数是 11 天。
以下代码的两个按钮的点击事件被吞了，自行添加上即可：
<div>
<input type="button" value="确定" onclick="onBtnClick()"/>
<input type="button" value="清除" onclick="onClearClick()"/>
</div>
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<title>Title</title>
<style>
label {
user-select: none;
}
</style>
</head>
<body>
<div>
<div>
<label>总运行次数
<input id="run-count-input" type="number" value="9"/>
</label>
</div>
<div>
<label>开始日期
<input id="start-date" type="date" value="2021-11-01"/>
</label>
</div>
<div>
<label>结束日期
<input id="end-date" type="date" value="2021-11-10"/>
</label>
</div>
<div>周期
<label>
<input id="week-1" type="checkbox" checked/>周一
</label>
<label>
<input id="week-2" type="checkbox" checked/>周二
</label>
<label>
<input id="week-3" type="checkbox"/>周三
</label>
<label>
<input id="week-4" type="checkbox"/>周四
</label>
<label>
<input id="week-5" type="checkbox" checked/>周五
</label>
<label>
<input id="week-6" type="checkbox"/>周六
</label>
<label>
<input id="week-0" type="checkbox" checked/>周日
</label>
<label>
<input id="sel-all" type="checkbox"/>全选
</label>
</div>
<div>
<label>
<input id="cross-day" type="checkbox" checked/>跨天
</label>
</div>
<div>
<input type="button" value="确定"/>
<input type="button" value="清除"/>
</div>
</div>
<script src="https://cdn.staticfile.org/moment.js/2.9.0/moment.min.js"></script>
<script>
let runCountInput = document.getElementById('run-count-input')
let startInput = document.getElementById('start-date')
let endInput = document.getElementById('end-date')
let weekInput = []
for (let i = 0; i < 7; i++) {
weekInput.push(document.getElementById('week-' + i))
}
let crossDayInput = document.getElementById('cross-day')
let outputDiv = []
function onSelAllChange(checked) {
weekInput.forEach(input => input.checked = checked)
}
function onClearClick() {
while (outputDiv.length) {
let div = outputDiv.pop()
div.parentNode.removeChild(div)
}
}
function onBtnClick() {
let weeks = []
weekInput.forEach((input, index) => {
if (input.checked) weeks.push(index)
})
let crossDay = crossDayInput.checked
let runCount = Number(runCountInput.value)
let start = moment(startInput.value), end = moment(endInput.value)
let rangeDays = end.diff(start, 'day') + 1
let maxDays = getMaxAvailableDays(runCount, crossDay, start, end, weeks)
let div = document.createElement('div')
let needCount = getNeedRunCount(crossDay, getConsecutiveDaysMap(start, end, weeks))
div.innerText = `总共${runCount}次，至少需要${needCount}次，${runCount >= needCount ? '' : '不'}符合；指定${rangeDays}天，最多${maxDays}天。`
document.body.appendChild(div)
outputDiv.push(div)
}
function getMaxAvailableDays(runCount, cross, start, end, weeks) {
if (weeks.length >= 7) {
let taskDays = end.diff(start, 'days') + 1
if (cross) runCount--
return Math.min(runCount, taskDays)
}
let map = getConsecutiveDaysMap(start, end.clone().add(7, 'days'), weeks)
let runDays = 0, noRunDays = 0
for (let key in map) {
let range = map
if (cross) runCount--
let rangeDays = range.end.diff(range.start, 'days') + 1
noRunDays = Number(key)
if (runCount > 0) runDays += Math.min(runCount, rangeDays)
runCount -= rangeDays
if (runCount < 0) break
}
return runDays + noRunDays
}
function getNeedRunCount(cross, map) {
let runCount = 0;
for (let key in map) {
let range = map
runCount += range.end.diff(range.start, 'days') + 1
if (cross) runCount++
}
return runCount
}
function getConsecutiveDaysMap(start, end, weeks) {
let map = {}, key = 0
if (weeks.length < 7) {
for (let date = start.clone(); !date.isAfter(end); date.add(1, 'days')) {
if (weeks.includes(date.day())) {
if (!map) {
map = {start: date.clone(), end: null}
}
map.end = date.clone()
} else {
key++
}
}
} else {
map = {start: start.clone(), end: end.clone()}
}
return map
}
</script>
</body>
</html> 没看懂需求啥意思 lucklys 发表于 2021-12-1 09:25
没看懂需求啥意思
看懂了看懂了 太麻烦, 我选择cron哈哈 lucklys 发表于 2021-12-1 09:30
看懂了看懂了
我还是看不懂，哈哈哈哈哈哈哈
页:
[1]