通信管道时间段的容量

通信管道时间段的容量
第二轮：通信管道的总容量固定。管道的class里面有个函数是外部可以每次请求某个时间段用多少容量，设计这个class。
先花了20多分钟讨论 然后20分钟写代码 应该不是最优解 问印度小哥有啥其他结构优化 小哥说没时间了 你自己回家想...

根据原楼主的题干加个例子：比如某网络供应商的bandwith是1TB/second。请求的单位也是秒。

第一个人请求8:14-9:00 200GB/sec. 批准
第二个人请求8:30-9:20 800GB/sec. 批准
这时候，8:30-9:00已经饱和。
第三个人请求8:00-10:30 1MB/sec. 因为涵盖了饱和的区间。否决

应该是线段树，先求min，再lazy update。

https://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=508669
http://massivealgorithms.blogspot.com/2018/05/leetcode-732-my-calendar-iii.html

    private TreeMap<Integer, Integer> timeline = new TreeMap<>();
    public int book(int s, int e) {
        timeline.put(s, timeline.getOrDefault(s, 0) + 1); // 1 new event will be starting at [s]
        timeline.put(e, timeline.getOrDefault(e, 0) - 1); // 1 new event will be ending at [e];
        int ongoing = 0, k = 0;
        for (int v : timeline.values())
            k = Math.max(k, ongoing += v);
        return k;
    }




因为有种O（n）的办法很简单 想知道是不是线段树更优。

正好拿来练一练最近自己归纳的线段树模板，话说不是应该找输入范围的最大值，看看加入delta后会不会超过，不会超过再lazy update吗

import collections

class SegTree:

    def __init__(self, N):

        self.N, self.ROOT = N, 1

        self.tree = collections.defaultdict(int)

        self.chg = collections.defaultdict(int)

    def query(self, start, end):

        def _query(lo, hi, ID):

            if end < lo or hi < start: return 0

            if start <= lo and hi <= end:

                return self.tree[ID] + self.chg[ID]

            m = (lo+hi)//2

            lres = _query(lo, m, ID*2)

            rres = _query(m+1, hi, ID*2+1)

            return max(lres, rres) + self.chg[ID]

        return _query(0, self.N, self.ROOT)

    def update(self, start, end, delta):

        def _update(lo, hi, ID):

            if end < lo or hi < start: return

            if start <= lo and hi <= end:

                self.chg[ID] += delta

                return

            m = (lo+hi)//2

            _update(lo, m, ID*2)

            _update(m+1, hi, ID*2+1)

            self.tree[ID] = max(self.tree[ID*2]+self.chg[ID*2], self.tree[ID*2+1]+self.chg[ID*2+1])

        _update(0, self.N, self.ROOT)

 

class Storage:

    def __init__(self, max_bandwith):

        self.max_bandwith = max_bandwith

        self.seg = SegTree(24*3600)

    def request(self, start, end, bandwith):

        if self.seg.query(start, end) + bandwith > self.max_bandwith:

            return False

        self.seg.update(start, end, bandwith)

        return True

 

import unittest

class TestStorage(unittest.TestCase):

 

    def test_1(self):

        storage = Storage(1000*1024)

        assert storage.request(1000, 2000, 800*1024) == True

        assert storage.request(1600, 2500, 200*1024) == True

        assert storage.request(900, 3500, 1) == False

        assert storage.request(1200, 1700, 1) == False

        assert storage.request(1900, 2200, 1) == False

        assert storage.request(988, 999, 1) == True

        assert storage.request(1000, 1001, 1) == True

        assert storage.request(2000, 2001, 1) == False

        assert storage.request(2001, 2002, 1) == True

        assert storage.request(1599, 1600, 1) == False

        assert storage.request(1600, 1600, 1) == False

        assert storage.request(1599, 1599, 1) == True

 

unittest.main()