如何调度考生的座位 :: labuladong的算法小抄

[utterances-bot]

文章链接点这里：如何调度考生的座位

评论礼仪 见这里，违者直接拉黑。

[fkjkkll]

这题我用一个堆解决的，由于C++的堆不够灵活，所以直接用vector，借助push_heap、pop_heap再加上自己实现的自定义堆操作，达成双100%，(●'◡'●)。思路就是借助这个堆来维护可用区间，seat和leave都是logN复杂度

[gutouyu]

可以提供一个c++版本么，按照思路写了一个，一直没有跑通。。。

class ExamRoom {
public:

    int N; // 记录座位总数量

    int distance(const pair<int,int>& a) {
        // 返回中点和两个端点最近的距离
        int len = (a.second - a.first) / 2;
        if(a.first == -1) {
            return a.second;
        }
        if(a.second == N) {
            return a.first;
        }
        return len;
    };

    struct comp {
        bool operator()(pair<int,int>& a, pair<int,int>& b) {
            int distA = distance(a);
            int distB = distance(b);
            // 如果长度相等，那就取index小的
            if(distA == distB) {
                return a.first < b.first;
            }
            // 根据线段长度，从大到小排序
            return distA > distB;
        };
    };
    set<pair<int, int>, comp> pq; //根据线段长度，从小到大存储所有线段

    unordered_map<int, pair<int,int>> startMap; // 以p开头的线段
    unordered_map<int, pair<int,int>> endMap; // 以p结尾的线段

    // 增加一个线段
    void addInterval(const pair<int,int>& p) {
        startMap.insert({p.first, p});
        endMap.insert({p.second, p});
        pq.insert(p);
    }

    // 删除一个线段
    void delInterval(const pair<int,int>& p) {
        pq.erase(p);
        startMap.erase(p.first);
        endMap.erase(p.second);
    }

    ExamRoom(int n) {
        N = n;

        // 存放一个虚拟线段[-1, N]
        addInterval({-1, N});
    }

    int seat() {
        // 选出最长的线段来
        pair<int,int> interval = *pq.begin();
        int x = interval.first, y = interval.second;

        // 找到线段中点,也就是seat的位置
        int seat;
        if(x == -1) {
            seat = 0;
        } else if (y == N) {
            seat = N - 1;
        } else {
            seat = (x + y) / 2;
        }

        // 删除这个线段, 并插入两个新的线段
        delInterval(interval);
        addInterval({x, seat});
        addInterval({seat, y});

        // 返回选择的座位
        return seat;
    }

    void leave(int p) {
        // 找到两段的线段
        pair<int,int> left = endMap[p];
        pair<int,int> right = startMap[p];

        // 删除这两个线段，并插入一个新的线段
        pair<int,int> newInterval = {left.first, right.second};
        delInterval(left);
        delInterval(right);
        addInterval(newInterval);
    }
};

[fornobugworld]

困难题细节太多了。。

[7chosen]

C++版的

class ExamRoom {
private:
    set<int>seats;
    int maxSeat;
public:
    ExamRoom(int n) {
        maxSeat=n;
    }

    int seat() {
        if(seats.empty()){
            seats.insert(0);
            return 0;
        }
        if(seats.size()==1){
            int fir=*(seats.begin());
            if(maxSeat-1-fir>fir){
                seats.insert(maxSeat-1);
                return maxSeat-1; 
            }else{
                seats.insert(0);
                return 0;
            }
        }
        int pos=0,now=-1;
        int maxdis=-1;
        for(auto s:seats){
            int dis=(s-now)/2;
            if(dis>maxdis){
                maxdis=dis;
                pos= now==-1 ? 0:now+maxdis;
            }
            now=s;
        }
        if(maxdis==0){
            seats.insert(maxSeat-1);
            return maxSeat-1;
        }
        else{
            seats.insert(pos);
            return pos;
        }
    }

    void leave(int p) {
        seats.erase(p);
    }
};

[massiachan]

写了一个只用一个TreeSet的版本， Java

class ExamRoom {
    private TreeSet<Integer> occupied;
    private int max;
    public ExamRoom(int n) {
        occupied = new TreeSet<>();
        max = n - 1;
    }

    public int seat() {
        if(occupied.isEmpty()) {
            occupied.add(0);
            return 0;
        } 
        int l = 0, r = 0;
        int pre = -1;
        int maxDist = 0;
        for(int i : occupied) {
            if(pre == -1 && i != 0) {
                maxDist = i;
                l = 0;
                r = 0;
                pre = i;
                continue;
            }
            int curDist = (i - pre) / 2;
            if(curDist > maxDist) {
                maxDist = curDist;
                l = pre;
                r = i;
            }
            pre = i;
        }
        if(pre < max && max - pre > maxDist) {
            l = max;
            r = max;
        }
        int next = l + (r - l) / 2;
        occupied.add(next);
        return next;
    }

    public void leave(int p) {
        occupied.remove(p);
    }
}

[deepbreath373]

check in

[l2009312042]

@gutouyu 我在你代码上改了一下 可以编译过

static int inum = 10;
int distance(const pair<int,int>& a) {
        // 返回中点和两个端点最近的距离
        int len = (a.second - a.first) / 2;
        if(a.first == -1) {
            return a.second;
        }
        if(a.second == inum) {
            return inum - 1- a.first;
        }
        return len;
    };

struct Line {
    bool operator()(const pair<int,int>& a, const pair<int,int>& b) const {
        int distA = distance(a);
        int distB = distance(b);
        // 如果长度相等，那就取index小的
        if(distA == distB) {
            return a.first < b.first;
        }
        // 根据线段长度，从大到小排序
        return distA > distB;
    };
};

class ExamRoom {
public:

    int N; // 记录座位总数量

    set<pair<int,int>,Line> pq; //根据线段长度，从小到大存储所有线段

    unordered_map<int, pair<int,int>> startMap; // 以p开头的线段
    unordered_map<int, pair<int,int>> endMap; // 以p结尾的线段

    // 增加一个线段
    void addInterval(const pair<int,int>& p) {
        startMap.insert({p.first, p});
        endMap.insert({p.second, p});
        pq.insert(p);
    }

    // 删除一个线段
    void delInterval(const pair<int,int>& p) {
        pq.erase(p);
        startMap.erase(p.first);
        endMap.erase(p.second);
    }

    ExamRoom(int n) {
        N = n;
        inum = n;

        // 存放一个虚拟线段[-1, N]
        addInterval({-1, N});
    }

    int seat() {
        // 选出最长的线段来
        pair<int,int> interval = *pq.begin();
        int x = interval.first, y = interval.second;

        // 找到线段中点,也就是seat的位置
        int seat;
        if(x == -1) {
            seat = 0;
        } else if (y == N) {
            seat = N - 1;
        } else {
            seat = (x + y) / 2;
        }

        // 删除这个线段, 并插入两个新的线段
        delInterval(interval);
        addInterval({x, seat});
        addInterval({seat, y});

        // 返回选择的座位
        return seat;
    }

    void leave(int p) {
        // 找到两段的线段
        pair<int,int> left = endMap[p];
        pair<int,int> right = startMap[p];

        // 删除这两个线段，并插入一个新的线段
        pair<int,int> newInterval = {left.first, right.second};
        delInterval(left);
        delInterval(right);
        addInterval(newInterval);
    }
};

[mengbingrock]

Python 版本的，自定义带删除功能的堆。直接在heapq上包了一层，更好的办法是参考labuladong堆的实现文章里的方法。 startMap 和 endMap定义稍有不同，搞的有点复杂。

class MyHeap:
    def __init__(self):
        self.data = []
        self.deleted = set()

    def top(self):
        self.lazy_deletion()
        return self.data[0]

    def pop(self):
        self.lazy_deletion()
        return heapq.heappop(self.data)

    def delete(self, key):
        self.deleted.add(key)

    def push(self, key):

        if key in self.deleted:
            self.deleted.remove(key)
        heapq.heappush(self.data, key)

    def lazy_deletion(self):

        while self.data and self.data[0] in self.deleted:            
            deletednode = heapq.heappop(self.data)
            self.deleted.remove(deletednode)

    def is_empty(self):
        return self.data is None

class ExamRoom:

    def __init__(self, n: int):
        self.heap = MyHeap()
        self.startMap = dict()
        self.endMap = dict()
        self.num = 0
        self.cap = n
        self.insertIntv(0,self.cap-1)

    def insertIntv(self,start,end):
        #print("insert",start, end)
        if start == 0:
            self.heap.push((-(end),start, end))
        elif end == self.cap - 1:
            self.heap.push((-1*((self.cap - 1 - start)),start,end))
        else:
            self.heap.push(((-1*((end - start)//2), start, end)))   
        self.startMap[start] = end
        self.endMap[end] = start

    def delIntv(self, start, end):   
        #print("delete",start,end)     
        del self.endMap[end]
        del self.startMap[start]
        if start == 0:
            self.heap.delete((-(end),start, end))
        elif end == self.cap - 1:
            self.heap.delete((-1*((self.cap - start)),start,end))
        else:
            self.heap.delete(((-1*((end - start)//2), start, end)))

    def seat(self) -> int:
        if self.num >= self.cap:
            return -1

        interval,start,end = self.heap.pop()

        if start == 0:
            mid = 0
        elif end == self.cap - 1 :

            mid = self.cap -1
        else:
            mid = (start + end)//2

        self.num += 1

        self.delIntv(start,end)

        if mid - 1 >= start:
            self.insertIntv(start, mid - 1)
        if end >= mid + 1:
            self.insertIntv(mid + 1, end)

        return mid

    def leave(self, p: int) -> None:

        if p > 0 and p < self.cap - 1:

            leftstart = self.endMap.get(p-1,p)
            leftend = p - 1 if p - 1 in self.endMap else p

            if p -1 in self.endMap:

                self.delIntv(leftstart,leftend)

            rightend = self.startMap.get(p+1,p)
            rightstart = p + 1 if p + 1 in self.startMap else p

            if p+1 in self.startMap:

                self.delIntv(rightstart, rightend)

            self.insertIntv(leftstart,rightend)

        if p == 0:

            leftend = self.startMap.get(1,p)
            leftstart = 1 if 1 in self.startMap else p
            if 1 in self.startMap:
                self.delIntv(leftstart,leftend)
            self.insertIntv(0,leftend)
        if p == self.cap - 1:
            #print("p=",self.cap - 1,self.endMap)
            rightstart = self.endMap.get(p-1,p)
            rightend = p - 1 if p - 1 in self.endMap else p
            if p - 1 in self.endMap:
                self.delIntv(rightstart, rightend)

            self.insertIntv(rightstart,p)

        self.num -= 1