发表于 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)

• LC 题目链接