From Gossip@caterpillar

Algorithm Gossip: 最大訪客數

說明

現將舉行一個餐會，讓訪客事先填寫到達時間與離開時間，為了掌握座位的數目，必須先估計不同時間的最大訪客數。

解法

這個題目看似有些複雜，其實相當簡單，單就計算訪客數這個目的，同時考慮同一訪客的來訪時間與離開時間，反而會使程式變得複雜；只要將來訪時間與離開時間分開處理就可以了，假設訪客 i 的來訪時間為x[i]，而離開時間為y[i]。

在資料輸入完畢之後，將x[i]與y[i]分別進行排序（由小到大），道理很簡單，只要先計算某時之前總共來訪了多少訪客，然後再減去某時之前的離開訪客，就可以輕易的解出這個問題。

實作

#include <stdio.h> 
#include <stdlib.h> 
#define MAX 100 
#define SWAP(x,y) {int t; t = x; x = y; y = t;} 

int partition(int[], int, int); 
void quicksort(int[], int, int); // 快速排序法
int maxguest(int[], int[], int, int); 

int main(void) { 
    int x[MAX] = {0}; 
    int y[MAX] = {0}; 
    int time = 0; 
    int count = 0; 

    printf("\n輸入來訪與離開125;時間(0~24)："); 
    printf("\n範例：10 15"); 
    printf("\n輸入-1 -1結束"); 
    while(count < MAX) { 
        printf("\n>>"); 
        scanf("%d %d", &x[count], &y[count]); 
        if(x[count] < 0) 
            break; 
        count++; 
    } 

    if(count >= MAX) { 
        printf("\n超出最大訪客數(%d)", MAX); 
        count--; 
    } 

    // 預先排序 
    quicksort(x, 0, count); 
    quicksort(y, 0, count); 

    while(time < 25) { 
        printf("\n%d 時的最大訪客數：%d", 
                   time, maxguest(x, y, count, time)); 
        time++; 
    } 

    printf("\n"); 

    return 0; 
} 

int maxguest(int x[], int y[], int count, int time) { 
    int i, num = 0; 

    for(i = 0; i <= count; i++) { 
        if(time > x[i]) 
            num++; 
        if(time > y[i]) 
            num--; 
    } 

    return num; 
} 

int partition(int number[], int left, int right) { 
    int i, j, s; 

    s = number[right]; 
    i = left - 1; 

    for(j = left; j < right; j++) { 
        if(number[j] <= s) { 
            i++; 
            SWAP(number[i], number[j]); 
        } 
    } 

    SWAP(number[i+1], number[right]); 
    return i+1; 
} 

void quicksort(int number[], int left, int right) { 
    int q; 

    if(left < right) { 
        q = partition(number, left, right); 
        quicksort(number, left, q-1); 
        quicksort(number, q+1, right); 
    } 
}

Java

import java.io.*;
import java.util.*;

public class MaxVisit {
    public static int maxGuest(int[] x, int[] y, int time) {
        int num = 0; 

        for(int i = 0; i < x.length; i++) { 
            if(time > x[i]) 
                num++; 
            if(time > y[i]) 
                num--; 
        } 

        return num; 
    }
    
    public static void main(String[] args) throws IOException {
        BufferedReader buf = new BufferedReader(
                new InputStreamReader(System.in));
        System.out.println("輸入來訪時間與離開時間(0~24)：");
        System.out.println("範例：10 15"); 
        System.out.println("輸入-1結束");
        
        java.util.ArrayList list = new ArrayList();
        
        while(true) { 
            System.out.print(">>"); 
            String input = buf.readLine();
            
            if(input.equals("-1")) 
                break; 
            
            list.add(input);
        }
        
        int[] x = new int[list.size()];
        int[] y = new int[list.size()];
        
        for(int i = 0; i < x.length; i++) {
            String input = (String) list.get(i);
            String[] strs = input.split(" ");
            
            x[i] = Integer.parseInt(strs[0]);
            y[i] = Integer.parseInt(strs[1]);
        }
        
        Arrays.sort(x);
        Arrays.sort(y);
        
        for(int time = 0; time < 25; time++) { 
            System.out.println(time + " 時的最大訪客數：" 
                    + MaxVisit.maxGuest(x, y, time)); 
        } 
    }
}