英文:
Validating free time slot in schedule
问题
我正在尝试设计一个高效的算法来完成以下任务，最好使用JavaScript或Golang编写：
给定一组繁忙的时间间隔（以毫秒为单位的开始时间戳+结束时间戳），验证要安排的传入时间段是否有效。假设不存在任何重叠。
示例：
const timeslots = [
{ start: 10, end: 14 },
{ start: 17, end: 21 },
{ start: 30, end: 37 },
// ...
];
const ts = timeslots.sort((a, b) => {
return a.start - b.start;
});
const checkValid = (inc) => {
// 在这里进行验证
};
console.log(checkValid({ start: 15, end: 16 })); // 应该为true
console.log(checkValid({ start: 15, end: 18 })); // 应该为false
console.log(checkValid({ start: 16, end: 27 })); // 应该为false
console.log(checkValid({ start: 8, end: 39 })); // 应该为false
并且应该适用于其他未描述的边缘情况。
英文:
I am trying to come up with an efficient algorithm to do the following, ideally in javascript or golang:
Given a set of busy time intervals (start timestamp + end timestamp in ms), validate an incoming timeslot to be scheduled. Assume there aren't any existing overlaps.
Example:
const timeslots = [
{ start: 10, end: 14 },
{ start: 17, end: 21 },
{ start: 30, end: 37 },
// ...
];
const ts = timeslots.sort((a, b) => {
return a.start - b.start;
});
const checkValid = (inc) => {
// validation here
};
console.log(checkValid({ start: 15, end: 16 })); // should be true
console.log(checkValid({ start: 15, end: 18 })); // should be false
console.log(checkValid({ start: 16, end: 27 })); // should be false
console.log(checkValid({ start: 8, end: 39 })); // should be false
And any other edge cases not described should work as well.
答案1
得分: 2
如果区间满足以下条件：(1) 不重叠且(2) 已排序，那么你可以使用二分查找来找到紧接在所需区间之后的第一个区间，然后简单地检查前一个区间是否与其重叠。这样的时间复杂度为O(logN)，而不是O(N)。
Go语言示例：
package main
import (
"fmt"
"sort"
)
type Slot struct {
start int
end int
}
var timeslots = []Slot{
{start: 10, end: 14},
{start: 17, end: 21},
{start: 30, end: 37},
}
func checkValid(slot Slot) bool {
i := sort.Search(len(timeslots), func(i int) bool {
return timeslots[i].start > slot.end
})
return i == 0 || timeslots[i-1].end < slot.start
}
func main() {
sort.Slice(timeslots, func(a, b int) bool {
return timeslots[a].start < timeslots[b].start
})
fmt.Println(checkValid(Slot{start: 15, end: 16})) // 应该为true
fmt.Println(checkValid(Slot{start: 15, end: 18})) // 应该为false
fmt.Println(checkValid(Slot{start: 16, end: 27})) // 应该为false
fmt.Println(checkValid(Slot{start: 8, end: 39})) // 应该为false
}
英文:
If the intervals are (1) non-overlapping and (2) sorted then you can perform a binary search to find the first one that lies just after the desired interval, and then simply check if the previous one overlaps with it. This would be O(logN) instead of O(N).
Example in Go:
package main
import (
"fmt"
"sort"
)
type Slot struct {
start int
end int
}
var timeslots = []Slot{
{start: 10, end: 14},
{start: 17, end: 21},
{start: 30, end: 37},
}
func checkValid(slot Slot) bool {
i := sort.Search(len(timeslots), func(i int) bool {
return timeslots[i].start > slot.end
})
return i == 0 || timeslots[i-1].end < slot.start
}
func main() {
sort.Slice(timeslots, func(a, b int) bool {
return timeslots[a].start < timeslots[b].start
})
fmt.Println(checkValid(Slot{start: 15, end: 16})) // should be true
fmt.Println(checkValid(Slot{start: 15, end: 18})) // should be false
fmt.Println(checkValid(Slot{start: 16, end: 27})) // should be false
fmt.Println(checkValid(Slot{start: 8, end: 39})) // should be false
}
答案2
得分: -1
翻译结果如下：
验证(start, end)
对于timeslots中的每个时间段
如果 start >= timeslot["start"] 并且 start <= timeslot["end"]
返回 false
如果 start < timeslot["start"] 并且 end >= timeslot["start"]
返回 false
如果 end >= timeslot["start"] 并且 end <= timeslot["end"]
返回 false
返回 true
我认为这样的代码应该可以工作。
英文:
validate(start, end)
for timeslot in timeslots
if start >= timeslot["start"] and start <= timeslot["end"]
return false
if start < timeslot["start"] and end >= timeslot["start"]
return false
if end >= timeslot["start"] and end <= timeslot["end"]
return false
return true
I think something like this should work.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论