想请教一道scheduling的算法题

之前oa遇到了这道题不太会做，发上来请教一下大家

input two array arrival and departure，arrival[i] and departure[i] are i th person's arrival date and departure date respectively. Each day you can only meet one person. Find the max number of purple you can meet before they leave.

EX: arrival = {1,2,2,3}, departure = {2,2,3,4}, then return 4 because you can meet person0 on day1, person1 on day2, person2 on day3, person3 on day4. However, if arrival = {2,2,2,3}, departure = {2,3,4,4} then return 3.

之前乍一看以为是经典的interval scheduling problem用greedy select earliest end time的，但这道题不一样那么做是不对的，想问问大家有什么想法吗？

isabuster1127 发表于 2019/11/23 02:23:37
这道题应该是一个matching problem啊， 如果greedy select 的话像是[1,5],[2,2],[...

如果当前只有一个interval , 选当前的interval, 否则选end最小的
day1: 选[1,5]
2:[2,2]
3:[3,4]
4:[4,4]
5:[4,5]

这不就是按照结束时间的Greedy Algorithm吗？没明白哪里不一样了？

1 所有区间数组 按 arrival 排升序，如果arrival相同按departute 排
2 index =0 开始  维护一个包含当前index的所有区间的heap，heap 按照 departure排序
set里所有 departure < index 的出堆删除
当前 区间arrival==index的入堆 ，从区间数组中删除
此时heap 不为空的话 count++ 然后pop departure最小的区间
3 if heap 不为空 index++
    else index为区间数组的 最小arrival

DP + backtracking ~= bruce force

LC類題就是 1235

就是greedy吧
暴力搜索应该是超时的

WKelvinson 发表于 2019-11-22 13:31
这不就是按照结束时间的Greedy Algorithm吗？没明白哪里不一样了？

这道题应该是一个matching problem啊， 如果greedy select 的话像是[1,5],[2,2],[3,4],[4,4][4,5]你每次select以后怎么判断你要用这个interval里的哪一天呢？如果最后选到[1,5]optimal情况下这个人安排在第一天，但你是最后一个select到这个interval的，不可能去loop一遍找哪天还没有被安排过吧