# 50066. Hotel Manager

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

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.

1234typedef struct RoomStatus {    int capacity;    struct Reservation *reservation;} RoomStatus;

123456typedef 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

1int 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.

### reservation.h

123456789101112131415161718#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)

12345678910111213141516171819202122232425#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

1gcc -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 201601033 20160103 201601054 20160102 201601042 20160101 201601032 20160101 201601023 20160102 201601053 20160101 201601044 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       ---