椁愰ギ鎺掗槦绠＄悊绯荤粺锛氶珮骞跺彂鍦烘櫙涓嬬殑闃熷垪浼樺寲鏂规

2.1 鏍稿績鏁版嵁缁撴瀯閫夋嫨

鎴戜滑閲囩敤涓夌鏁版嵁缁撴瀯鐨勭粍鍚堟柟妗堬細

interface WaitingParty {
    partyId: string;      // 鍞竴鏍囪瘑
    partySize: number;    // 浜烘暟
    arrivalTime: number;  // 鍒拌揪鏃堕棿鎴?
    isActive: boolean;    // 鏄惁浠嶅湪绛夊緟
}

class WaitlistManager {
    // 1. 鏈夊簭闃熷垪锛氱淮鎶ゅ埌杈鹃『搴?
    private queue: WaitingParty[] = [];
    
    // 2. 蹇€熷畾浣嶈〃锛歱artyId -> 闃熷垪绱㈠紩
    private indexMap: Map<string, number> = new Map();
    
    // 3. 浜烘暟鍒嗘《锛歴ize -> 璇ヤ汉鏁扮殑绛夊緟缁勫垪琛?
    private sizeBuckets: Map<number, Set<string>> = new Map();
    
    // 4. 鏈€澶т汉鏁颁笂闄愶紙鐢ㄤ簬閬嶅巻浼樺寲锛?
    private readonly MAX_PARTY_SIZE = 20;
}

2.2 鍔犲叆闃熷垪鎿嶄綔

joinWaitlist(partyId: string, partySize: number): void {
    const party: WaitingParty = {
        partyId,
        partySize,
        arrivalTime: Date.now(),
        isActive: true
    };
    
    // 鍔犲叆闃熷垪灏鹃儴
    const index = this.queue.length;
    this.queue.push(party);
    
    // 鏇存柊绱㈠紩鏄犲皠
    this.indexMap.set(partyId, index);
    
    // 鍔犲叆浜烘暟鍒嗘《
    if (!this.sizeBuckets.has(partySize)) {
        this.sizeBuckets.set(partySize, new Set());
    }
    this.sizeBuckets.get(partySize)!.add(partyId);
}

2.3 绂诲紑闃熷垪鎿嶄綔锛堟噿鍒犻櫎锛?/h3>

leaveWaitlist(partyId: string): boolean {
    const index = this.indexMap.get(partyId);
    if (index === undefined) return false;
    
    const party = this.queue[index];
    if (!party.isActive) return false;
    
    // 鏍囪涓洪潪娲昏穬锛堟噿鍒犻櫎锛?
    party.isActive = false;
    
    // 浠庡垎妗朵腑绉婚櫎
    this.sizeBuckets.get(party.partySize)?.delete(partyId);
    
    // 浠庣储寮曡〃绉婚櫎
    this.indexMap.delete(partyId);
    
    return true;
}

馃挕 鎳掑垹闄ょ瓥鐣ワ細涓嶅疄闄呯Щ鍔ㄦ暟缁勫厓绱狅紝鑰屾槸鏍囪涓洪潪娲昏穬銆傝繖鏍峰垹闄ゆ搷浣滀负O(1)锛屼唬浠锋槸鏌ヨ鏃堕渶瑕佽烦杩囧凡鍒犻櫎椤广€?

2.4 鎸夊閲忓尮閰嶏紙鏍稿績绠楁硶锛?/h3>

findFirstFitParty(tableCapacity: number): WaitingParty | null {
    // 鏂规涓€锛氶亶鍘嗛槦鍒楋紝鎵剧涓€涓鍚堟潯浠剁殑娲昏穬缁?
    for (const party of this.queue) {
        if (party.isActive && party.partySize <= tableCapacity) {
            return party;
        }
    }
    return null;
}

// 浼樺寲鏂规锛氬埄鐢ㄥ垎妗跺揩閫熺瓫閫?
findFirstFitPartyOptimized(tableCapacity: number): WaitingParty | null {
    // 鏀堕泦鎵€鏈夌鍚堜汉鏁版潯浠剁殑partyId
    const candidates: string[] = [];
    
    for (let size = 1; size <= tableCapacity && size <= this.MAX_PARTY_SIZE; size++) {
        const bucket = this.sizeBuckets.get(size);
        if (bucket) {
            candidates.push(...bucket);
        }
    }
    
    if (candidates.length === 0) return null;
    
    // 鎸夊埌杈炬椂闂存帓搴忥紝杩斿洖鏈€鏃╃殑
    let earliest: WaitingParty | null = null;
    let earliestTime = Infinity;
    
    for (const partyId of candidates) {
        const index = this.indexMap.get(partyId);
        if (index !== undefined) {
            const party = this.queue[index];
            if (party.isActive && party.arrivalTime < earliestTime) {
                earliest = party;
                earliestTime = party.arrivalTime;
            }
        }
    }
    
    return earliest;
}

涓夈€佸鏉傚害瀵规瘮鍒嗘瀽

鍏朵腑 n 涓洪槦鍒楅暱搴︼紝k 涓虹鍚堟潯浠剁殑鍊欓€夋暟閲?/em>