JZX轻语：简
LeetCode 2589 - 完成所有任务的最少时间
发表于2024年05月15日
对于任务规划题目，一般都可以采取按结束时间排序 + 贪心的方法解决。在这个问题里，同样可以先按end排序，然后遍历所有的任务，首先优先寻找能够复用的时间段，即使用start对已经使用的时间occupied(离散时间点，如[1,2,3,5,6,7]表示时间[1-3]和[5-7]被使用，且可以复用)进行二分搜索，寻找大于等于start的元素下标位置i，此时可以复用的时间段数量为occupied.length() - i(即右侧的所有时间都可以复用)；对于剩下的、无法复用的时间，则将其依次添加到occupied中（新建使用时间），直至所有任务处理完毕，返回occupied的长度即可。
需要注意的是，新插入的时间不一定全是连续的，比如任务(3, 12, 5)插入到已使用的时间数组[10,11]时，能够复用的时间为10,11，而插入的元素为12,9,8！因此，需要维护一个set来便于查询某时间是否已经占用了。
上述注意点对应的测试样例为[[10,16,3],[10,20,5],[1,12,4],[8,11,2]]。
class Solution:
def shiftingLetters(self, s: str, shifts: List[int]) -> str:
# 反向前缀和?
ord_a = ord('a') # 预计算a的ascii
suffix_sum = [0] * len(shifts)
acc_sum = 0
for i in range(len(shifts) - 1, -1, -1):
acc_sum = (acc_sum + shifts[i]) % 26 # 在这里mod 26
suffix_sum[i] = acc_sum
ans = []
for i in range(len(s)):
# 注意这里的小写字母移位
new_ord = ord_a + ((ord(s[i]) - ord_a) + suffix_sum[i]) % 26
ans.append(chr(new_ord))
return ''.join(ans)