[Introduction to Algorithm]The hiring problem

[wutiejun]

Suppose that you need to hire a new office assistant. Your previous attempts at hiring have been unsuccessful, and you decide to use an employment agency. The employment agency sends you one candidate each day. You interview that person and then decide either to hire that person or not. You must pay the employment agency a small fee to interview an applicant. To actually hire an applicant is more costly, however, since you must fire your current office assistant and pay a substantial hiring fee to the employment agency. You are committed to having, at all times, the best possible person for the job. Therefore, you decide that, after interviewing each applicant, if that applicant is better qualified than the current office assistant, you will fire the current office assistant and hire the new applicant. You are willing to pay the resulting price of this strategy, but you wish to estimate what that price will be.

[wutiejun]

HIRE_Assistant(n)
best = 0 // candidate 0 is a least-qualified dummy candidate
for i = 1 to n
    interview candidate i
    if candidate i is better than candidate best
        best = i
        hire candidate i

[wutiejun]

Worst-case analysis

In the worst case, we actually hire every candidate that we interview. This situation occurs if the candidates come in strictly increasing order of quality, in which case we hire n times, for a total hiring cost of O.chn/.

[wutiejun]

HIRE_Assistant(n)
randomy permute the list of candidates
best = 0 // candidate 0 is a least-qualified dummy candidate
for i = 1 to n
    interview candidate i
    if candidate i is better than candidate best
        best = i
        hire candidate i

[wutiejun]

// intorduction-to-algorithm
//
// hiring assistant
//

#include "stdio.h"
#include <stdlib.h>
#include <string.h>
#include <sys/time.h>
//int gettimeofday(struct timeval *restrict tp, void *restrict tzp);

int RandomScore()
{
    static int inted = 0;
    struct timeval tp;
    gettimeofday(&tp, NULL);
    int val = tp.tv_usec;
    //srandom(tp.tv_usec%32);
    //val = random();
    if(inted == 0)
    {
        srand((unsigned)time(NULL));
        inted = 1;
    }
    val = rand();
    return (val%100);
}

void HIRE_Assistant(int candidates[], unsigned char hired[], int max)
{
    int best = -1;
    int i;
    for (i = 0; i < max; i ++)
    {
        if (candidates[i] > best)
        {
            best = candidates[i];
            hired[i] = 1;
        }
    }
    return;
}

int * InitArray(int Num)
{
    int * pArray = malloc(sizeof(int) * Num);
    int i;
    for (i = 0; i < Num; i ++ )
    {
        pArray[i] = RandomScore();
    }
    return pArray;
}

void PrintItemArray(int *  pA, int len, const char * pInfo)
{
    int i;
    printf("============%s===============\r\n", pInfo);
    for(i = 0; i < len; i ++)
    {
        printf("%d:%d\r\n", i, pA[i]);
    }
    return;
}

void PrintHiredInfo(int pArray[], unsigned char pHired[], int max)
{
    int i;
    printf("Hired info:\r\n");
    for (i = 0; i < max; i ++ )
    {
        if(pHired[i] == 1)
        {
            printf("[%d]:%d ", i, pArray[i]);
        }
    }
    printf("\r\n");
    return;
}

int main(int argc, char * argv[])
{
    if (argc < 2)
    {
        printf("Please input array count to test sort.\r\n");
        return 0;
    }

    int max = atoi(argv[1]);
    if (max <= 0)
    {
        max = 1;
    }
    int * pArray = InitArray(max);
    unsigned char * pHired = malloc(sizeof(unsigned char) * max);

    HIRE_Assistant(pArray, pHired, max);

    PrintItemArray(pArray, max, "raw info");
    PrintHiredInfo(pArray, pHired, max);

    return 0;
}