50066. Hotel Manager

I'm a slow walker, but I never walk backwards.

Task Description

Write a function to manage reservations of a hotel.

Given a list of hotel rooms and requests of reservations for hotel rooms, write a function ReserveRoom to manage the hotel, and put the result into an array of structure RoomStatus.

A room is defined by a structure RoomStatus. It contains the number of people that can stay in this room and a pointer pointing to a linked list of reservation (structure Reservation) of that room. A reservation consisting of the number of people that will stay in this room, and the starting and the ending dates of the reservation.

1
2
3
4
typedef struct RoomStatus {
    int capacity;
    struct Reservation *reservation;
} RoomStatus;
1
2
3
4
5
6
typedef struct Reservation {
    int nP;
    int StartTime;
    int EndTime;
    struct Reservation *next;
} Reservation;

At the beginning, the reservation pointer in every RoomStatus will be the NULL, which means there are no reservations. Then, there will be given reservation requests, and each contains the number of people, starting time, and ending time of a reservation request. You have to find the first room which can accommodate the number of people (capacity $\geq$ # of people) and has not been reserved for the period of time in the request. If you can find such a room, you should insert this reservation request into the linked list reservation so that the reservations are ordered by increasing StartTime. Note that, if the time period of a request overlaps with previous reservations, then it is invalid. It is guaranteed that in a request the StartTime will be earlier than EndTime. Note that if the ending time of one request is the same as the starting time of the next request, both request are valid. If function ReserveRoom find a suitable room for the request, it returns 1, otherwise it returns 0.

The prototype of the function you need to implement is as follows

1
int ReserveRoom(RoomStatus List[], int nR, int nP, int StartTime, int EndTime);

nR is the number of room in the List[], and nP is the number of people in the request.

Header and Main Program

reservation.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#ifndef _RESERVATION_H
#define _RESERVATION_H
 
typedef struct RoomStatus {
    int capacity;
    struct Reservation *reservation;
} RoomStatus;
 
typedef struct Reservation {
    int nP;
    int StartTime;
    int EndTime;
    struct Reservation *next;
} Reservation;
 
int ReserveRoom(RoomStatus list[], int n, int nP, int StartTime, int EndTime);
 
#endif

main.c(test)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include "reservation.h"
#include <stdio.h>
#include <stdlib.h>
 
int main(){
    int n = 3;
    RoomStatus list[n];
    for(int i=0; i < n; i++){
        list[i].capacity = i+2;
        list[i].reservation = NULL;
    }
    int nP, sTime, eTime;
    while(scanf("%d %d %d", &nP, &sTime, &eTime)!=EOF)
        printf("%d", ReserveRoom(list, n, nP, sTime, eTime));
    puts("");
    printf("---Room Status List---\n");
    for(int i=0; i<n; i++){
        printf("%d ---", list[i].capacity);
        for(Reservation *tmp = list[i].reservation; tmp!=NULL; tmp=tmp->next)
            printf("->(%d:%d, %d)", tmp->nP, tmp->StartTime, tmp->EndTime);
        puts("");
    }
    printf("---      End       ---\n");
    return 0;
}

Compile

1
gcc -std=c99 -O2 reservation.c main.c -lm

Input Format

Input contains one testcase, and the amounts of reserved request. Each line is one request until the end of file (EOF). Each request contains number of people, StartTime, and EndTime. It’s guaranteed that StartTime and EndTime won’t be the same.

Output Format

Print the return value of all reserved request in one line. Then print out the status of all rooms in the hotel. The linked list containing Reservation in each RoomStatus must be sorted by the increasing StartTime. Moreover, make sure that each linked list is ended with NULL pointer.

Sample Input

2 20160101 20160103
3 20160103 20160105
4 20160102 20160104
2 20160101 20160103
2 20160101 20160102
3 20160102 20160105
3 20160101 20160104
4 20160105 20160110

Sample Output

11111001
---Room Status List---
2 ---->(2:20160101, 20160103)
3 ---->(2:20160101, 20160103)->(3:20160103, 20160105)
4 ---->(2:20160101, 20160102)->(4:20160102, 20160104)->(4:20160105, 20160110)
---      End       ---

Discussion