我的日程安排系列问题(区间重叠问题)

 文章目录

• 1.插旗法
• 2.求重复区间数量的通用模板
• 3.日程安排系列问题的通用模板
• 4.我的日程安排I
• 5.我的日程安排II
• 6.我的日程安排III
• 7.总结

问题说明

关于力扣上我的日程安排问题的插旗解法

插旗法

先来介绍一下插旗法：进入一个区间的时候将该点坐标对应的值+1，代表插上一面进入的🚩，离开时将该点坐标值-1，代表插上一面离开的🚩，在同一个点可以同时插进入的旗或离开的旗，因为这样并不形成区间重叠。时间复杂度控制在 O(nlogn)

举例子 
[10, 15) 
[12, 18)

插旗子 计数
<10, 1> 
<12, 1>
<15, -1>
<18, -1>
如果 两个Interval 不相交，则 连续两个 插旗计数的 和 必然等于零，一个+1，一个-1     
 如果 两个 Interval 相交，则 连续两个插旗计数 的和 必然大于0，一个+1，一个+1 

给出求重复区间数量的通用模板(C++)

int maxConcurrent (vecotr>& time){
    map record;
    for(auto& t : time){
        record[t[0]] += 1;
        record[t[1]] -= 1;
    }
    int ans = 0, concurrent = 0;
    for(auto& p : record){
        concurrent += p.second;
        ans = max(ans, concurrent);
    }
    return ans;
}

代码解读

代码中采用map形式存储键值对,其中第一个for循环目的是遍历整个输入数据,进而得到如实例中所示的<10,1>形式.需要注意的是,在进入第二个for循环之前,要求Map有序(键值增加),这样才能正确的统计区间的旗子数量.这种方法更像是给区间加上左右括号,进入🚩就是左括号，出去🚩就是右括号，左右🚩可以抵消，就像左右括号可以抵消一样.

给出日程安排系列问题的通用模板(C++)

class MyCalendar {
public:
    map rec;

    MyCalendar() {}
    
    bool book(int start, int end) {
        rec[start] += 1;
        rec[end] -= 1;
        int cur = 0;

        for(auto& p : rec){
            cur += p.second;
            if(cur > 1){   // 根据具体问题(重复区间数量)来决定cur取值范围
                rec[start]--, rec[end]++;
                return false;
            }
        }
        return true;
    }
};

代码解读

在解决日程安排系列问题中,同样要求进入for循环之前的Map是有序的,和求重复区间不同的是,在for循环内部不在取当前区间数量和已有区间数量的最大值,而是判断区间值的累加和与给定取值范围大小的关系.

---

我的日程安排表 I

实现一个 MyCalendar 类来存放你的日程安排。如果要添加的日程安排不会造成 重复预订 ，则可以存储这个新的日程安排。

当两个日程安排有一些时间上的交叉时（例如两个日程安排都在同一时间内），就会产生 重复预订 。

日程可以用一对整数 start 和 end 表示，这里的时间是半开区间，即 [start, end), 实数 x 的范围为，  start <= x < end 。

Python代码

from sortedcontainers import SortedDict
class MyCalendar:

    def __init__(self):
        self.dict = SortedDict()

    def book(self, start: int, end: int) -> bool:
        self.dict[start] = self.dict.setdefault(start, 0) + 1
        self.dict[end] = self.dict.setdefault(end, 0) - 1
        temp_cur = 0
        for key, value in self.dict.items():
            temp_cur += value
            if temp_cur > 1 :
                self.dict[start] -= 1
                self.dict[end] += 1
                return False
        return True

​

需要注意的是,在开头引入了SortedDict, SortedDict和OrderDict是不一样的,OrderDict只保证字典中的键是按照插入顺序排列的,而SortedDict是保证字典中的元素是按照键值增序排列.

在第二个函数开始部分使用了self.dict.setdefault(start,0),这部分代码的含义为设置默认初始值为0,python中的dict修改value值的 *** 作过程中,如果dict中没有指定的key值,直接进行value+1是会报错的,同样也可以采用在init函数中将dict初始化为defaultdict(int)的形式,这样,dict的默认值是0.若使用sorted函数在对dict进行排序之后,注意得到的是一个列表,想将列表转换为字典要使用dict(list)的形式.

dict_new=sorted(dic1.items(),key=lambda dic1:dic1[1])
dict(dict_new)

在for循环中使用temp_cur来记录重叠区间的个数,因为要求不能有重复区间,所以当temp_cur > 1时,是不合理的,要返回False.

Java代码

class MyCalendar {
    private TreeMap cnt; 
    public MyCalendar() {
        cnt = new TreeMap();
    }
    
    public boolean book(int start, int end) {
        int ans = 0;
        int maxBook = 0;
        cnt.put(start, cnt.getOrDefault(start, 0) + 1);
        cnt.put(end, cnt.getOrDefault(end, 0) - 1);
        for (Map.Entry entry : cnt.entrySet()) {
            int freq = entry.getValue();
            maxBook += freq;
            if (maxBook > 1){
                cnt.put(start, cnt.getOrDefault(start, 0) - 1);
                cnt.put(end, cnt.getOrDefault(end, 0) + 1);
                return false;
            }
        }
        return true;
    }
}

---

我的日程安排表 II

实现一个 MyCalendar 类来存放你的日程安排。如果要添加的时间内不会导致三重预订时，则可以存储这个新的日程安排。

MyCalendar 有一个 book(int start, int end)方法。它意味着在 start 到 end 时间内增加一个日程安排，注意，这里的时间是半开区间，即 [start, end), 实数 x 的范围为，  start <= x < end。

当三个日程安排有一些时间上的交叉时（例如三个日程安排都在同一时间内），就会产生三重预订。

每次调用 MyCalendar.book方法时，如果可以将日程安排成功添加到日历中而不会导致三重预订，返回 true。否则，返回 false 并且不要将该日程安排添加到日历中。

Python代码

from sortedcontainers import SortedDict
class MyCalendarTwo:

    def __init__(self):
        self.dict = SortedDict()

    def book(self, start: int, end: int) -> bool:
        self.dict[start] = self.dict.setdefault(start, 0) + 1
        self.dict[end] = self.dict.setdefault(end, 0) - 1
        temp_cur = 0
        for key, value in self.dict.items():
            temp_cur += value
            if temp_cur > 2 :
                self.dict[start] -= 1
                self.dict[end] += 1
                return False
        return True

Java代码

class MyCalendarTwo {
    private TreeMap cnt;  
    public MyCalendarTwo() {
        cnt = new TreeMap();
    }
    
    public boolean book(int start, int end) {
        int ans = 0;
        int maxBook = 0;
        cnt.put(start, cnt.getOrDefault(start, 0) + 1);
        cnt.put(end, cnt.getOrDefault(end, 0) - 1);
        for (Map.Entry entry : cnt.entrySet()) {
            int freq = entry.getValue();
            maxBook += freq;
            if (maxBook > 2){
                cnt.put(start, cnt.getOrDefault(start, 0) - 1);
                cnt.put(end, cnt.getOrDefault(end, 0) + 1);
                return false;
            }
        }
        return true;

    }
}

代码解读

从代码可以看出,如果使用插旗法,则和我的日程安排I仅仅在for循环中的if判断语句部分进行了修改.可以说非常相似了.

---

我的日程安排表 III

当 k 个日程安排有一些时间上的交叉时（例如 k 个日程安排都在同一时间内），就会产生 k 次预订。

给你一些日程安排 [start, end) ，请你在每个日程安排添加后，返回一个整数 k ，表示所有先前日程安排会产生的最大 k 次预订。

与前两道题不同,在力扣上这是一道hard题,个人感觉hard主要在读懂题意上(hhhh).本体解法和上两题不同,采用的是寻找区间数量的模板.

Python代码

from sortedcontainers import SortedDict
class MyCalendarThree:
    def __init__(self):
        self.d = SortedDict()

    def book(self, start: int, end: int) -> int:
        self.d[start] = self.d.setdefault(start, 0) + 1
        self.d[end] = self.d.setdefault(end, 0) - 1

        ans = maxBook = 0
        for freq in self.d.values():
            maxBook += freq
            ans = max(ans, maxBook)
        return ans

Java代码

class MyCalendarThree {
    private TreeMap cnt;

    public MyCalendarThree() {
        cnt = new TreeMap();
    }
    
    public int book(int start, int end) {
        int ans = 0;
        int maxBook = 0;
        cnt.put(start, cnt.getOrDefault(start, 0) + 1);
        cnt.put(end, cnt.getOrDefault(end, 0) - 1);
        for (Map.Entry entry : cnt.entrySet()) {
            int freq = entry.getValue();
            maxBook += freq;
            ans = Math.max(maxBook, ans);
        }
        return ans;
    }
}

总结

本文介绍了插旗法解决我的日程安排的系列问题,其实就是对区间重复问题的不断使用与总结,对于区间问题的重叠,可以通过判断Map的value值的累计和与要求最多重叠次数的大小来进行比较,而对于求具体的重叠区间数量,则可以用一个ans来记录当前最大的重叠区间数的形式来进行累和.使用本方法的时候要尤其注意的是在遍历求value值的时候,要将Map按照键值升序排序! 当然本体亦可通过线段树等方式进行求解,时间复杂度会进一步降低,但是代码相对难以理解,需要后期的不断学习.