最大訪客數

說明

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

解法

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

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

實作：C Java Python Scala Ruby JavaScript Haskell

#include <stdio.h> 
#include <stdlib.h> 
#include <time.h> 

#define GUESTS 30

int compare(const void*, const void*);
int max(int[][GUESTS], int, int); 

int main(void) { 
    srand(time(NULL)); 
    
    int visits[2][GUESTS] = {0};
    
    int i;
    for(i = 0; i < GUESTS; i++) {
        visits[0][i] = (double) rand() / RAND_MAX * 24;
        visits[1][i] = (double) rand() / RAND_MAX * 
            (24 - visits[0][i]) + visits[0][i];
    }

    // 預先排序 
    qsort(visits[0], GUESTS, sizeof(int), compare);
    qsort(visits[1], GUESTS, sizeof(int), compare);

    int t;
    for(t = 0; t < 24; t++) {
        int num = max(visits, GUESTS, t);
        if(num != 0) {
            printf("%2d 時訪客數：%2d 位\n", t, num); 
        }             
    }
    
    return 0; 
} 

int compare(const void* a, const void* b) {
    return *(int*)a - *(int*)b;
}

int max(int visits[][GUESTS], int count, int time) { 
    int num, i;
    for(num = 0, i = 0; i <= count; i++) {
        num = time > visits[0][i] ? num + 1 : num;
        num = time > visits[1][i] ? num - 1 : num;
    } 
    return num; 
}

Java

import java.util.*;
import static java.lang.System.out;
import static java.util.Arrays.*;
import static java.lang.Math.random;

class Visitor {
    final int start;
    final int end;
    public Visitor(int start, int end) {
        this.start = start;
        this.end = end;
    }
}

public class Visitors {
    private List<Visitor> visitors = new ArrayList<>();
    
    public void add(Visitor v) {
        visitors.add(v);
    }
    
    public int max(int time) {
        return max(time, sortedSE());
    }
    
    public int[] max() {
        int[][] se = sortedSE();
        int[] timeList = new int[24];
        for(int t = 0; t < 24; t++) { 
            timeList[t] = max(t, se);
        } 
        return timeList;
    }
    
    private int[][] sortedSE() {
        int[][] se = new int[2][visitors.size()];
        for(int i = 0; i < visitors.size(); i++) {
            se[0][i] = visitors.get(i).start;
            se[1][i] = visitors.get(i).end;
        }
        sort(se[0]);
        sort(se[1]);
        return se;
    }
    
    private int max(int time, int[][] se) {
        int num = 0; 
        for(int i = 0; i < se[0].length; i++) { 
            num = time > se[0][i] ? num + 1 : num;
            num = time > se[1][i] ? num - 1 : num;
        } 
        return num;        
    }
    
    public static void main(String[] args) {
        final int GUESTS = 30;
        Visitors visitors = new Visitors();
        for(int i = 0; i < GUESTS; i++) {
            int start = (int) (random() * 24);
            int end = (int) (start + random() * (24 - start));
            visitors.add(new Visitor(start, end));
        }
    
        int[] guests = visitors.max();
        for(int t = 0; t < 24; t++) { 
            out.printf("%2d 時訪客：%2d 位%n", t, guests[t]); 
        } 
    }
}

Python

from functools import reduce
from random import random

def max(visits, time):
    return reduce(lambda num, t: num - 1 if time > t else num, visits[1],
        reduce(lambda num, t: num + 1 if time > t else num, visits[0] , 0))
        
GUESTS = 30
starts = [int(random() * 24) for i in range(GUESTS)]
ends = [int(random() * (24 - start) + start) for start in starts]

visits = [sorted(starts), sorted(ends)]
for t in range(24):
    num = max(visits, t)
    if num != 0:
        print("%2d 時訪客：%2d 位" % (t, num))

Scala

import java.lang.Math._

def max(visits: List[List[Int]], time: Int) = {
    ((0 /: visits(0)) {(num, t) => if(time > t) num + 1 else num} 
        /: visits(1)) {(num, t) => if(time > t) num - 1 else num}
}

val GUESTS = 30
val starts = for(i <- 0 until GUESTS) yield (random * 24).toInt
val ends = for(start <- starts) yield 
               (random * (24 - start) + start).toInt

val visits = List(starts.sortWith(_ > _).toList, ends.sortWith(_ > _).toList)
for(
    t <- 0 until 24;
    num = max(visits, t)
    if num != 0
) { printf("%2d 時訪客：%2d 位%n", t, num) }

Ruby

#encoding: Big5
def max(visits, time)
    visits[1].reduce(
        visits[0].reduce(0) {|num, t| time > t ? num + 1 : num }
    ) {|num, t| time > t ? num - 1 : num}
end
        
GUESTS = 30
starts = (0...GUESTS).map {(rand * 24).to_i}
ends = starts.map {|start| (rand * (24 - start) + start).to_i}

visits = [starts.sort, ends.sort]
(0...24).each do |t|
    num = max(visits, t)
    if num != 0
        printf("%2d 時訪客：%2d 位\n", t, num)
    end
end

JavaScript

function max(visits, time) {
    var num = 0;
    for(var t = 0; t < visits[0].length; t++) {
        num = time > visits[0][t] ? num + 1 : num;
        num = time > visits[1][t] ? num - 1 : num;
    }
    return num;
}

var GUESTS = 30;
var visits = [[], []];
for(var i = 0; i < GUESTS; i++) {
    visits[0][i] = parseInt(Math.random() * 24);
    visits[1][i] = parseInt(Math.random() * 
                     (24 - visits[0][i]) + visits[0][i]);
}
var result = '';
for(var t = 0; t < 24; t++) {
    num = max(visits, t);
    if(num != 0) { result += (t + '時訪客：' + num + '位\n'); }
}
print(result);

Haskell

import System.Random
import Control.Monad
import Text.Printf

rand gen n= take n \$ randomRs (0.0, 1.0) gen::[Float]

maxV visits time = foldl (count (-))
    (foldl (count (+)) 0 (visits !! 0)) (visits !! 1)
    where count op num t = if time > t then num `op` 1 else num

main = do
    gen1 <- getStdGen
    gen2 <- newStdGen
    let guests = 30
        starts = map (truncate . (* 24)) (rand gen1 guests)
        rs = (rand gen1 guests)
        ends = [truncate ((rs !! i) * fromIntegral(
            24 - (starts !! i))) + (starts !! i)| i <- [0..guests - 1]]
        visits = [starts, ends]
    print visits
    forM [0..23] (\t -> do
        let num = maxV visits t
        printf "%2d has %2d guests\n" (t::Int) (num::Int))