如何调度考生的座位 :: 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);
    }
};

[syumet]

class ExamRoom {

    struct Comparator {
        int N;

        Comparator(int n) : N(n) {}

        int dist(const pair<int, int>& p) const {
            if (p.first == -1) return p.second;
            if (p.second == N) return N - 1 - p.first;
            return (p.second - p.first) / 2;
        }

        bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs) const {
            if (dist(lhs) == dist(rhs)) {
                return lhs.first < rhs.first;
            } 
            return dist(lhs) > dist(rhs);         
        }
    };

    unordered_map<int, int> l2r;
    unordered_map<int, int> r2l;
    set<pair<int, int>, Comparator>* segments = nullptr;
    int cap;

    void removeInterval(const int lt, const int rt) {
        segments->erase({lt, rt});
        l2r.erase(lt);
        r2l.erase(rt);
    }

    void addInterval(const int lt, const int rt) {
        segments->insert({lt, rt});
        l2r[lt] = rt;
        r2l[rt] = lt;
    }

public:
    ExamRoom(int n) {
        cap = n;
        segments = new set<pair<int, int>, Comparator>(Comparator(n));
        segments->insert({-1, n});
    }

    ~ExamRoom() {
        delete segments;
    }
    
    int seat() {
        auto p = segments->begin();
        int lt = p->first, rt = p->second;
        int seat;
        if (lt == -1) { // 情况一
            seat = 0;
        } else if (rt == cap) { // 情况二
            seat = cap - 1;
        } else { // 情况三
            seat = (lt + rt) / 2;
        }
        removeInterval(lt, rt);
        addInterval(lt, seat);
        addInterval(seat, rt);
        return seat;
    }
    
    void leave(int p) {
        int lt = r2l[p], rt = l2r[p];
        removeInterval(lt, p);
        removeInterval(p, rt);
        addInterval(lt, rt);
    }
};

你需要生成一个comparator实例,并把N作为参数传入

[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

[yonggui-yan]

打卡，打卡。依赖数据结构。

对每个边，需要知道左右端点，还需要知道线段的长度。

然后这些边要可以总是取到最大的。这些边还得可以删除。

删除一个学生，需要知道端点对应的边。

[yonggui-yan]

排序应该是按照插入新生后离两端的最短距离排序，而不是线段本身的长度。

[caobojia]

private int distance(int[] intv) {
int x = intv[0];
int y = intv[1];
if (x == -1) return y;
if (y == N) return N - 1 - x;
// 中点和端点之间的长度
return (y - x) / 2;
}

有点没明白 既然算的是中点和端点之间的长度，
if (x == -1) return y;
if (y == N) return N - 1 - x;
为啥还要有这两个if呢？

[fwb-flandre]

我的理解是，当端点值为-1和N时，所取的中点就是0和N-1，因此中点和端点之间的长度就是y和N - 1 - x。

[taojiangcb]

seat:
// 将最长的线段分成两段
int[] left = new int[] {x, seat};
int[] right = new int[] {seat, y};
removeInterval(longest);
addInterval(left);
addInterval(right);

leav：
// 将 p 左右的线段找出来
int[] right = startMap.get(p);
int[] left = endMap.get(p);
// 合并两个线段成为一个线段
int[] merged = new int[] {left[0], right[1]};

这个为什么两个是反着的？

[LKJ-np]

public void leave(int p) {
// 将 p 左右的线段找出来
int[] right = startMap.get(p);
int[] left = endMap.get(p);
// 合并两个线段成为一个线段
int[] merged = new int[] {left[0], right[1]};
removeInterval(left);
removeInterval(right);
addInterval(merged);
}
中int[] merged = new int[] {left[0], right[1]};出现空指针异常，这里是不是有问题呢
java.lang.NullPointerException: Cannot load from int array because "" is null
at line 74, ExamRoom.leave
at line 65, Driver.helperSelectMethod
at line 86, Driver.helper
at line 107, Driver.main