List of activities X71187
At the end of the problem statement you will find a half-implemented program which you have to finish. In particular, two functions in the program are incomplete. The following text explains the data with which the functions work and what they do.
The program works with a data type Activity, which represents an activity, including a name, the starting time (t1), and the ending time (t2). To simplify, t1 and t2 are integer variables, and the program always works with activites with correct times, t1<t2:
struct Activity {
string name;
int t1,t2;
};
The program also works with a data type ListActivities, which is a list of activities:
typedef vector<Activity> ListActivities;
The first function you will have to implement verifies that two activities are compatible, that is, they do not overlap in time. In the particular case that one activity ends exactly at the time when another starts, they will be considered compatible.
bool compatibleActivities(Activity a, Activity b)
The second function you have to implement receives two activities and returns true if the first is less than the second, according to the following criteria. An activity is less than another if it starts strictly before the other, or it starts at the same time and ends strictly before, or has the same start time and end time as the other but its name is less than the name of the other in lexicographical order.
bool smallerActivity(Activity a, Activity b)
The previous function is used from another point in the program to sort all activities.
Finish the following code to solve the problem:
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
// Here you can add more includes if you wish.
using namespace std;
struct Activity {
string name;
int t1, t2; // t1<t2 must be satisfied for a correct activity
};
typedef vector<Activity> ListActivities;
// Auxiliary functions (you can add more functions if you wish)
// Pre: The input contains a description of an activity with the format:
//
// name t1 t2
//
// where name is a non-empty string with lowercase letters and t1<t2
// Post: Returns the activity read from the input adapted to the format of struct Activity.
Activity readActivity()
{
Activity a;
cin >> a.name >> a.t1 >> a.t2;
return a;
}
// Pre: listactivities represents a list of correct activities
// Post: Prints all activities from first to last, one per line, and with the format:
//
// name t1 t2
void printActivities(const ListActivities &listactivities)
{
for (int i = 0; i < int(listactivities.size()); i++) {
const Activity &a = listactivities[i];
cout << a.name << " " << a.t1 << " " << a.t2 << endl;
}
}
// Pre: a, b represent correct activities.
// Post: Returns true iff the activities have a compatible timeline,
// i.e. they do not overlap in time.
// Note: if one of them finishes exactly when the other starts, then they are compatible.
bool compatibleActivities(Activity a, Activity b)
{
// Implement this function.
// ...
}
// Pre: a, b represent correct activities.
// Post: Returns true iff one of the following conditions holds:
// - a starts strictly before b.
// - a and b start at the same time but a finishes before b.
// - a and b coincide in start and end time, but a has lexicographically-smaller name than b.
bool smallerActivity(Activity a, Activity b)
{
// Implement this function.
// ...
}
int main()
{
ListActivities listactivities;
string command;
while (cin >> command) {
if (command == "NEW") {
listactivities.push_back(readActivity());
} else if (command == "SORT") {
sort(listactivities.begin(), listactivities.end(), smallerActivity);
} else if (command == "PRINT") {
cout << "Current list activities:" << endl;
printActivities(listactivities);
cout << endl;
} else if (command == "CHECKCOMPATIBLE") {
int i, j;
cin >> i >> j;
string namei = listactivities[i].name;
string namej = listactivities[j].name;
if (compatibleActivities(listactivities[i], listactivities[j]))
cout << "Activities " << namei << " and " << namej << " are compatible" << endl;
else
cout << "Activities " << namei << " and " << namej << " are incompatible" << endl;
cout << endl;
}
}
}
Input
The input consists of a list of commands to create activities, sort them, write all of them, and check if two are compatible. There is no need to worry about the input since the main function already calls the appropriate functions to interpret the commands.
Output
The output shows the results of the commands. There is no need to worry about the output much since the main, which is given, already calls the appropriate functions to produce the output.
Public test cases
Input
NEW biking 169 277 PRINT SORT NEW cinema 224 598 SORT PRINT NEW jogging 108 483 PRINT CHECKCOMPATIBLE 0 1 CHECKCOMPATIBLE 1 2 SORT PRINT NEW gym 24 184 NEW swimming 218 574 CHECKCOMPATIBLE 2 3 PRINT SORT NEW chatting 161 501 SORT NEW climbing 26 510 PRINT NEW reading 207 303 NEW siteseeing 440 561 PRINT NEW strolling 318 385 PRINT SORT PRINT CHECKCOMPATIBLE 1 7 NEW bowling 413 553 NEW boxing 42 253 PRINT NEW writing 77 154 PRINT SORT NEW flirting 84 320 PRINT NEW singing 281 548 CHECKCOMPATIBLE 6 7 PRINT CHECKCOMPATIBLE 4 9 CHECKCOMPATIBLE 1 5 NEW dancing 398 498 CHECKCOMPATIBLE 7 8 NEW shopping 28 58 PRINT CHECKCOMPATIBLE 3 5 CHECKCOMPATIBLE 0 13 SORT NEW cooking 182 530 CHECKCOMPATIBLE 6 14 PRINT NEW praying 54 433 SORT NEW fishing 435 599 PRINT CHECKCOMPATIBLE 9 14 SORT CHECKCOMPATIBLE 0 7 PRINT CHECKCOMPATIBLE 10 19 CHECKCOMPATIBLE 10 17 CHECKCOMPATIBLE 4 19 NEW hunting 380 465 PRINT CHECKCOMPATIBLE 2 4 CHECKCOMPATIBLE 0 17 CHECKCOMPATIBLE 11 13 SORT CHECKCOMPATIBLE 5 16 PRINT CHECKCOMPATIBLE 1 14 CHECKCOMPATIBLE 7 14 CHECKCOMPATIBLE 7 14 CHECKCOMPATIBLE 1 13 CHECKCOMPATIBLE 4 12 CHECKCOMPATIBLE 9 12 CHECKCOMPATIBLE 5 8 CHECKCOMPATIBLE 8 15 CHECKCOMPATIBLE 5 7 CHECKCOMPATIBLE 5 11 CHECKCOMPATIBLE 9 10 CHECKCOMPATIBLE 17 18 CHECKCOMPATIBLE 1 9 CHECKCOMPATIBLE 3 18 CHECKCOMPATIBLE 5 16 CHECKCOMPATIBLE 4 17 CHECKCOMPATIBLE 10 16 CHECKCOMPATIBLE 8 17 CHECKCOMPATIBLE 1 3 CHECKCOMPATIBLE 17 20 CHECKCOMPATIBLE 1 12 CHECKCOMPATIBLE 8 10 CHECKCOMPATIBLE 0 3 CHECKCOMPATIBLE 4 11 CHECKCOMPATIBLE 4 11 CHECKCOMPATIBLE 12 19 CHECKCOMPATIBLE 0 16 CHECKCOMPATIBLE 4 11 CHECKCOMPATIBLE 9 11
Output
Current list activities: biking 169 277 Current list activities: biking 169 277 cinema 224 598 Current list activities: biking 169 277 cinema 224 598 jogging 108 483 Activities biking and cinema are incompatible Activities cinema and jogging are incompatible Current list activities: jogging 108 483 biking 169 277 cinema 224 598 Activities cinema and gym are compatible Current list activities: jogging 108 483 biking 169 277 cinema 224 598 gym 24 184 swimming 218 574 Current list activities: gym 24 184 jogging 108 483 chatting 161 501 biking 169 277 swimming 218 574 cinema 224 598 climbing 26 510 Current list activities: gym 24 184 jogging 108 483 chatting 161 501 biking 169 277 swimming 218 574 cinema 224 598 climbing 26 510 reading 207 303 siteseeing 440 561 Current list activities: gym 24 184 jogging 108 483 chatting 161 501 biking 169 277 swimming 218 574 cinema 224 598 climbing 26 510 reading 207 303 siteseeing 440 561 strolling 318 385 Current list activities: gym 24 184 climbing 26 510 jogging 108 483 chatting 161 501 biking 169 277 reading 207 303 swimming 218 574 cinema 224 598 strolling 318 385 siteseeing 440 561 Activities climbing and cinema are incompatible Current list activities: gym 24 184 climbing 26 510 jogging 108 483 chatting 161 501 biking 169 277 reading 207 303 swimming 218 574 cinema 224 598 strolling 318 385 siteseeing 440 561 bowling 413 553 boxing 42 253 Current list activities: gym 24 184 climbing 26 510 jogging 108 483 chatting 161 501 biking 169 277 reading 207 303 swimming 218 574 cinema 224 598 strolling 318 385 siteseeing 440 561 bowling 413 553 boxing 42 253 writing 77 154 Current list activities: gym 24 184 climbing 26 510 boxing 42 253 writing 77 154 jogging 108 483 chatting 161 501 biking 169 277 reading 207 303 swimming 218 574 cinema 224 598 strolling 318 385 bowling 413 553 siteseeing 440 561 flirting 84 320 Activities biking and reading are incompatible Current list activities: gym 24 184 climbing 26 510 boxing 42 253 writing 77 154 jogging 108 483 chatting 161 501 biking 169 277 reading 207 303 swimming 218 574 cinema 224 598 strolling 318 385 bowling 413 553 siteseeing 440 561 flirting 84 320 singing 281 548 Activities jogging and cinema are incompatible Activities climbing and chatting are incompatible Activities reading and swimming are incompatible Current list activities: gym 24 184 climbing 26 510 boxing 42 253 writing 77 154 jogging 108 483 chatting 161 501 biking 169 277 reading 207 303 swimming 218 574 cinema 224 598 strolling 318 385 bowling 413 553 siteseeing 440 561 flirting 84 320 singing 281 548 dancing 398 498 shopping 28 58 Activities writing and chatting are compatible Activities gym and flirting are incompatible Activities jogging and dancing are incompatible Current list activities: gym 24 184 climbing 26 510 shopping 28 58 boxing 42 253 writing 77 154 flirting 84 320 jogging 108 483 chatting 161 501 biking 169 277 reading 207 303 swimming 218 574 cinema 224 598 singing 281 548 strolling 318 385 dancing 398 498 bowling 413 553 siteseeing 440 561 cooking 182 530 Current list activities: gym 24 184 climbing 26 510 shopping 28 58 boxing 42 253 praying 54 433 writing 77 154 flirting 84 320 jogging 108 483 chatting 161 501 biking 169 277 cooking 182 530 reading 207 303 swimming 218 574 cinema 224 598 singing 281 548 strolling 318 385 dancing 398 498 bowling 413 553 siteseeing 440 561 fishing 435 599 Activities biking and singing are compatible Activities gym and jogging are incompatible Current list activities: gym 24 184 climbing 26 510 shopping 28 58 boxing 42 253 praying 54 433 writing 77 154 flirting 84 320 jogging 108 483 chatting 161 501 biking 169 277 cooking 182 530 reading 207 303 swimming 218 574 cinema 224 598 singing 281 548 strolling 318 385 dancing 398 498 bowling 413 553 fishing 435 599 siteseeing 440 561 Activities cooking and siteseeing are incompatible Activities cooking and bowling are incompatible Activities praying and siteseeing are compatible Current list activities: gym 24 184 climbing 26 510 shopping 28 58 boxing 42 253 praying 54 433 writing 77 154 flirting 84 320 jogging 108 483 chatting 161 501 biking 169 277 cooking 182 530 reading 207 303 swimming 218 574 cinema 224 598 singing 281 548 strolling 318 385 dancing 398 498 bowling 413 553 fishing 435 599 siteseeing 440 561 hunting 380 465 Activities shopping and praying are incompatible Activities gym and bowling are compatible Activities reading and cinema are incompatible Activities writing and hunting are compatible Current list activities: gym 24 184 climbing 26 510 shopping 28 58 boxing 42 253 praying 54 433 writing 77 154 flirting 84 320 jogging 108 483 chatting 161 501 biking 169 277 cooking 182 530 reading 207 303 swimming 218 574 cinema 224 598 singing 281 548 strolling 318 385 hunting 380 465 dancing 398 498 bowling 413 553 fishing 435 599 siteseeing 440 561 Activities climbing and singing are incompatible Activities jogging and singing are incompatible Activities jogging and singing are incompatible Activities climbing and cinema are incompatible Activities praying and swimming are incompatible Activities biking and swimming are incompatible Activities writing and chatting are compatible Activities chatting and strolling are incompatible Activities writing and jogging are incompatible Activities writing and reading are compatible Activities biking and cooking are incompatible Activities dancing and bowling are incompatible Activities climbing and biking are incompatible Activities boxing and bowling are compatible Activities writing and hunting are compatible Activities praying and dancing are incompatible Activities cooking and hunting are incompatible Activities chatting and dancing are incompatible Activities climbing and boxing are incompatible Activities dancing and siteseeing are incompatible Activities climbing and swimming are incompatible Activities chatting and cooking are incompatible Activities gym and boxing are incompatible Activities praying and reading are incompatible Activities praying and reading are incompatible Activities swimming and fishing are incompatible Activities gym and hunting are compatible Activities praying and reading are incompatible Activities biking and reading are incompatible
Input
NEW biking 1 3 PRINT NEW cinema 2 3 CHECKCOMPATIBLE 0 1 PRINT NEW jogging 0 3 NEW gym 1 3 PRINT NEW swimming 2 3 PRINT CHECKCOMPATIBLE 2 3 CHECKCOMPATIBLE 3 4 CHECKCOMPATIBLE 1 4 CHECKCOMPATIBLE 1 3 NEW chatting 0 1 CHECKCOMPATIBLE 0 2 NEW climbing 1 2 NEW reading 0 1 NEW siteseeing 1 2 PRINT NEW strolling 0 1 CHECKCOMPATIBLE 2 7 CHECKCOMPATIBLE 3 6 CHECKCOMPATIBLE 0 7 PRINT CHECKCOMPATIBLE 2 7 CHECKCOMPATIBLE 0 8 SORT NEW bowling 0 1 CHECKCOMPATIBLE 4 10 PRINT NEW boxing 0 1 CHECKCOMPATIBLE 4 7 PRINT CHECKCOMPATIBLE 6 10 NEW writing 1 2 NEW flirting 1 3 SORT PRINT CHECKCOMPATIBLE 3 8 NEW singing 1 2 PRINT CHECKCOMPATIBLE 1 4 NEW dancing 1 3 NEW shopping 1 3 PRINT SORT CHECKCOMPATIBLE 0 3 CHECKCOMPATIBLE 5 11 NEW cooking 2 3 PRINT NEW praying 1 3 CHECKCOMPATIBLE 0 17 NEW fishing 0 3 PRINT SORT CHECKCOMPATIBLE 8 18 PRINT NEW hunting 0 3 SORT PRINT CHECKCOMPATIBLE 4 5 CHECKCOMPATIBLE 3 8 CHECKCOMPATIBLE 7 13 CHECKCOMPATIBLE 14 16 CHECKCOMPATIBLE 8 17 CHECKCOMPATIBLE 15 17 CHECKCOMPATIBLE 18 20 CHECKCOMPATIBLE 4 16 CHECKCOMPATIBLE 0 11 CHECKCOMPATIBLE 4 8 CHECKCOMPATIBLE 2 15 CHECKCOMPATIBLE 15 16 CHECKCOMPATIBLE 2 3 CHECKCOMPATIBLE 1 11 CHECKCOMPATIBLE 4 17 CHECKCOMPATIBLE 8 11 CHECKCOMPATIBLE 9 19 CHECKCOMPATIBLE 11 20 CHECKCOMPATIBLE 11 17 CHECKCOMPATIBLE 10 12 CHECKCOMPATIBLE 6 14 CHECKCOMPATIBLE 6 16 CHECKCOMPATIBLE 2 3 CHECKCOMPATIBLE 1 19 CHECKCOMPATIBLE 16 20 CHECKCOMPATIBLE 5 11 CHECKCOMPATIBLE 1 6 CHECKCOMPATIBLE 4 12 CHECKCOMPATIBLE 0 10 CHECKCOMPATIBLE 8 11 CHECKCOMPATIBLE 0 7 CHECKCOMPATIBLE 9 16 CHECKCOMPATIBLE 10 17 CHECKCOMPATIBLE 2 9 CHECKCOMPATIBLE 2 11 CHECKCOMPATIBLE 4 11 CHECKCOMPATIBLE 5 14 CHECKCOMPATIBLE 19 20 CHECKCOMPATIBLE 1 19
Output
Current list activities: biking 1 3 Activities biking and cinema are incompatible Current list activities: biking 1 3 cinema 2 3 Current list activities: biking 1 3 cinema 2 3 jogging 0 3 gym 1 3 Current list activities: biking 1 3 cinema 2 3 jogging 0 3 gym 1 3 swimming 2 3 Activities jogging and gym are incompatible Activities gym and swimming are incompatible Activities cinema and swimming are incompatible Activities cinema and gym are incompatible Activities biking and jogging are incompatible Current list activities: biking 1 3 cinema 2 3 jogging 0 3 gym 1 3 swimming 2 3 chatting 0 1 climbing 1 2 reading 0 1 siteseeing 1 2 Activities jogging and reading are incompatible Activities gym and climbing are incompatible Activities biking and reading are compatible Current list activities: biking 1 3 cinema 2 3 jogging 0 3 gym 1 3 swimming 2 3 chatting 0 1 climbing 1 2 reading 0 1 siteseeing 1 2 strolling 0 1 Activities jogging and reading are incompatible Activities biking and siteseeing are incompatible Activities climbing and bowling are compatible Current list activities: chatting 0 1 reading 0 1 strolling 0 1 jogging 0 3 climbing 1 2 siteseeing 1 2 biking 1 3 gym 1 3 cinema 2 3 swimming 2 3 bowling 0 1 Activities climbing and gym are incompatible Current list activities: chatting 0 1 reading 0 1 strolling 0 1 jogging 0 3 climbing 1 2 siteseeing 1 2 biking 1 3 gym 1 3 cinema 2 3 swimming 2 3 bowling 0 1 boxing 0 1 Activities biking and bowling are compatible Current list activities: bowling 0 1 boxing 0 1 chatting 0 1 reading 0 1 strolling 0 1 jogging 0 3 climbing 1 2 siteseeing 1 2 writing 1 2 biking 1 3 flirting 1 3 gym 1 3 cinema 2 3 swimming 2 3 Activities reading and writing are compatible Current list activities: bowling 0 1 boxing 0 1 chatting 0 1 reading 0 1 strolling 0 1 jogging 0 3 climbing 1 2 siteseeing 1 2 writing 1 2 biking 1 3 flirting 1 3 gym 1 3 cinema 2 3 swimming 2 3 singing 1 2 Activities boxing and strolling are incompatible Current list activities: bowling 0 1 boxing 0 1 chatting 0 1 reading 0 1 strolling 0 1 jogging 0 3 climbing 1 2 siteseeing 1 2 writing 1 2 biking 1 3 flirting 1 3 gym 1 3 cinema 2 3 swimming 2 3 singing 1 2 dancing 1 3 shopping 1 3 Activities bowling and reading are incompatible Activities jogging and dancing are incompatible Current list activities: bowling 0 1 boxing 0 1 chatting 0 1 reading 0 1 strolling 0 1 jogging 0 3 climbing 1 2 singing 1 2 siteseeing 1 2 writing 1 2 biking 1 3 dancing 1 3 flirting 1 3 gym 1 3 shopping 1 3 cinema 2 3 swimming 2 3 cooking 2 3 Activities bowling and cooking are compatible Current list activities: bowling 0 1 boxing 0 1 chatting 0 1 reading 0 1 strolling 0 1 jogging 0 3 climbing 1 2 singing 1 2 siteseeing 1 2 writing 1 2 biking 1 3 dancing 1 3 flirting 1 3 gym 1 3 shopping 1 3 cinema 2 3 swimming 2 3 cooking 2 3 praying 1 3 fishing 0 3 Activities singing and cooking are compatible Current list activities: bowling 0 1 boxing 0 1 chatting 0 1 reading 0 1 strolling 0 1 fishing 0 3 jogging 0 3 climbing 1 2 singing 1 2 siteseeing 1 2 writing 1 2 biking 1 3 dancing 1 3 flirting 1 3 gym 1 3 praying 1 3 shopping 1 3 cinema 2 3 cooking 2 3 swimming 2 3 Current list activities: bowling 0 1 boxing 0 1 chatting 0 1 reading 0 1 strolling 0 1 fishing 0 3 hunting 0 3 jogging 0 3 climbing 1 2 singing 1 2 siteseeing 1 2 writing 1 2 biking 1 3 dancing 1 3 flirting 1 3 gym 1 3 praying 1 3 shopping 1 3 cinema 2 3 cooking 2 3 swimming 2 3 Activities strolling and fishing are incompatible Activities reading and climbing are compatible Activities jogging and dancing are incompatible Activities flirting and praying are incompatible Activities climbing and shopping are incompatible Activities gym and shopping are incompatible Activities cinema and swimming are incompatible Activities strolling and praying are compatible Activities bowling and writing are compatible Activities strolling and climbing are compatible Activities chatting and gym are compatible Activities gym and praying are incompatible Activities chatting and reading are incompatible Activities boxing and writing are compatible Activities strolling and shopping are compatible Activities climbing and writing are incompatible Activities singing and cooking are compatible Activities writing and swimming are compatible Activities writing and shopping are incompatible Activities siteseeing and biking are incompatible Activities hunting and flirting are incompatible Activities hunting and praying are incompatible Activities chatting and reading are incompatible Activities boxing and cooking are compatible Activities praying and swimming are incompatible Activities fishing and writing are incompatible Activities boxing and hunting are incompatible Activities strolling and biking are compatible Activities bowling and siteseeing are compatible Activities climbing and writing are incompatible Activities bowling and jogging are incompatible Activities singing and praying are incompatible Activities siteseeing and shopping are incompatible Activities chatting and singing are compatible Activities chatting and writing are compatible Activities strolling and writing are compatible Activities fishing and flirting are incompatible Activities cooking and swimming are incompatible Activities boxing and cooking are compatible