Problem Links:
uva10191,Problem:
Problem D: Longest Nap
| Problem D: Longest Nap |
The Problem
As you may already know, there are professors very busy with a filled schedule of work during the day. Your professor, let's call him Professor P, is a bit lazy and wants to take a nap during the day, but as his schedule is very busy, he doesn't have a lot of chances of doing this. He would REALLY like, however, to take one nap every day. Because he'll take just one nap, he wants to take the longest nap that it's possible given his schedule. He decided to write a program to help him in this task but, as we said, Professor P is very lazy. So, he finally decided that YOU must write the program!The Input
The input will consist on an arbitrary number of test cases, each test case represents one day. The first line of each set contains a positive integer s (not greater than 100) representing the number of scheduled appointments during that day. In the next s lines there are the appointments in the following format:time1 time2 appointmentWhere time1 represents the time which the appointment starts and time2 the time it ends. All times will be in the hh:mm format, time1 will always be strictly less than time2, they will be separated by a single space and all times will be greater than or equal to 10:00 and less than or equal to 18:00. So, your response must be in this interval as well (i.e. no nap can start before 10:00 and last after 18:00). The appointment can be any sequence of characters, but will always be in the same line. You can assume that no line will be longer than 255 characters, that 10 <= hh <= 18 and that 0 <= mm < 60. You CAN'T assume, however, that the input will be in any specific order. You must read the input until you reach the end of file.
The Output
For each test case, you must print the following line:Day #d: the longest nap starts at hh:mm and will last for [H hours and] M minutes.Where d stands for the number of the test case (starting from 1) and hh:mm is the time when the nap can start. To display the duration of the nap, follow these simple rules:
- if the total duration X in minutes is less than 60, just print "M minutes", where M = X.
- if the total duration X in minutes is greater or equal to 60, print "H hours and M minutes", where H = X div 60 (integer division, of course) and M = X mod 60.
Sample Input
4 10:00 12:00 Lectures 12:00 13:00 Lunch, like always. 13:00 15:00 Boring lectures... 15:30 17:45 Reading 4 10:00 12:00 Lectures 12:00 13:00 Lunch, just lunch. 13:00 15:00 Lectures, lectures... oh, no! 16:45 17:45 Reading (to be or not to be?) 4 10:00 12:00 Lectures, as everyday. 12:00 13:00 Lunch, again!!! 13:00 15:00 Lectures, more lectures! 15:30 17:15 Reading (I love reading, but should I schedule it?) 1 12:00 13:00 I love lunch! Have you ever noticed it? :)
Sample Output
Day #1: the longest nap starts at 15:00 and will last for 30 minutes. Day #2: the longest nap starts at 15:00 and will last for 1 hours and 45 minutes. Day #3: the longest nap starts at 17:15 and will last for 45 minutes. Day #4: the longest nap starts at 13:00 and will last for 5 hours and 0 minutes.
© 2001 Universidade do Brasil (UFRJ). Internal Contest Warmup 2001.
Solution:
Sort + Greedy.Source Code:
//Fri Mar 18 01:34:43 CDT 2011#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
using namespace std;
class Time
{
public:
int start;
int end;
Time(int s, int m)
{
this->start = s;
this->end = m;
}
static bool cmp(const Time &A, const Time &B)
{
if (A.start < B.start) return true;
if (A.start == B.start && A.end > B.end) return true;
return false;
}
};
void initialize(int N, vector<Time> &v)
{
int a, b, c, d;
char ch;
string str;
for (int i = 0; i < N; i++)
{
getline(cin, str);
stringstream s(str);
s >> a >> ch >> b >> c >> ch >> d >> str;
//cout << a << b << c << d << str << endl;
v.push_back(Time((a - 10)*60 + b, (c - 10)*60 + d));
}
v.push_back(Time(480, 480));
}
Time solve(vector<Time> v)
{
int N = v.size();
//for (int i = 0; i < N; i++)
// cout << v[i].start << ":" << v[i].end << endl;
std::sort(v.begin(), v.end(), Time::cmp);
int mmax = 0;
int last = 0;
int mark = -1;
for (int i = 0; i < N; i++)
{
if (v[i].start > last)
{
if (v[i].start - last > mmax)
{
mmax = v[i].start - last;
mark = i - 1;
}
last = v[i].end;
}
else if (v[i].end > last)
last = v[i].end;
}
return Time(v[mark].end, mmax);
}
void print(int T, vector<Time> v)
{
Time t = solve(v);
int h = t.start / 60 + 10;
int m = t.start % 60;
cout << "Day #" << T << ": the longest nap starts at ";
cout << h << ":" << setw(2) << setfill('0') << m << " and will last for ";
int hh = t.end / 60;
int mm = t.end % 60;
if (hh > 0)
cout << hh << " hours and ";
cout << mm << " minutes." << endl;
}
int main(int argc, char* argv[])
{
//freopen("input.in", "r", stdin);
//freopen("output.out", "w", stdout);
int T = 1;
int N;
while (cin >> N)
{
getchar();
vector<Time> schedule;
initialize(N, schedule);
print(T++, schedule);
}
//fclose(stdin);
//fclose(stdout);
return 0;
}
No comments :
Post a Comment