[LC] 0732 My Calendar III

Java

import java.util.TreeMap;

/**
 * <a href="https://leetcode.cn/problems/my-calendar-iii/">My Calender III</a>
 * 设计；线段树；二分查找；有序集合；前缀和
 */

/**
 * 差分数组
 */
class MyCalendarThree {
    private final TreeMap<Integer, Integer> cnt;

    public MyCalendarThree() {
        cnt = new TreeMap<>();
    }

    public int book(int startTime, int endTime) {
        int res = 0;
        int maxBook = 0;
        cnt.put(startTime, cnt.getOrDefault(startTime, 0) + 1); // 从startTime开始的预定数目加1
        cnt.put(endTime, cnt.getOrDefault(endTime, 0) - 1); // 从endTime开始的预定数目减1
        for (var entry : cnt.entrySet()) {
            int freq = entry.getValue();    // 以起点x开始的预定的总数目为 \Sum_{i \le x} cnt[i]
            maxBook += freq;
            res = Math.max(maxBook, res);
        }
        return res;
    }
}

Go

import "sort"

type MyCalendarThree struct {
    cnt map[int]int
}

func Constructor() MyCalendarThree {
    return MyCalendarThree{cnt: make(map[int]int)}
}

func (t *MyCalendarThree) Book(startTime int, endTime int) int {
    res := 0
    maxBook := 0
    t.cnt[startTime]++
    t.cnt[endTime]--

    keys := make([]int, 0, len(t.cnt))
    for key := range t.cnt {
        keys = append(keys, key)
    }
    sort.Ints(keys)

    for _, key := range keys {
        freq := t.cnt[key] // 以起点x开始的预定的总数目为 \Sum_{i \le x} cnt[i]
        maxBook += freq
        if maxBook > res {
            res = maxBook
        }
    }
    return res
}