Этот вопрос был задан 4 апреля в google codejam: https://codingcompetitions.withgoogle.com/codejam/round/000000000019fd27/000000000020bdf9.
Описание вопроса:
Кэмерон и Джем ie малышу почти 3 года! Однако, несмотря на то, что ребенок теперь стал более независимым, планирование действий ребенка и домашних потребностей c по-прежнему является проблемой для пары.
Кэмерон и Джем ie имеют список из N действий, которые необходимо решить в течение дня. Каждое действие происходит в течение определенного интервала в течение дня. Им нужно назначить каждое действие одному из них, чтобы ни одно из них не отвечало за два перекрывающихся действия. Действие, которое заканчивается в момент времени t, не считается перекрывающимся с другим действием, которое начинается в момент времени t.
Например, предположим, что Jam ie и Кэмерон должны охватывать 3 действия: одно из которых выполняется с 18:00. до 20:00, еще с 19:00 до 21:00 и еще с 22:00 до 23:00. Одним из возможных вариантов будет то, что Jam ie будет охватывать деятельность, выполняемую с 19:00 до 21:00, а Кэмерон - две другие. Другим действительным расписанием будет то, что Кэмерон будет охватывать деятельность с 18:00 до 20:00, а Jam ie - две другие. Обратите внимание, что первые два действия перекрываются во времени между 19:00 и 20:00, поэтому невозможно назначить оба этих действия одному и тому же партнеру.
Учитывая время начала и окончания каждого действия, найдите любое расписание, которое не требует, чтобы один и тот же человек покрывал перекрывающиеся действия, или скажите, что это невозможно.
Входные данные В первой строке входных данных указано количество тестовых случаев, за которыми следуют T. Каждый тестовый пример начинается со строки, содержащей одно целое число N, количество действий для назначения. Затем следуют еще N строк. I-я из этих строк (начиная с 1) содержит два целых числа Si и Ei. I-е действие начинается ровно через Si минут после полуночи и заканчивается ровно через Ei минут после полуночи.
Выходные данные Для каждого тестового примера выведите одну строку, содержащую Case #x: y, где x - номер тестового случая (начиная с из 1) и y НЕВОЗМОЖНО, если нет действующего расписания в соответствии с вышеуказанными правилами, или строка из ровно N символов в противном случае. I-й символ в y должен быть C, если i-тое действие назначено Кэмерону в предложенном расписании, и J, если он назначен на Jam ie.
Если существует несколько решений , вы можете вывести любой из них.
Input :
4
3
360 480
420 540
600 660
3
0 1440
1 3
2 4
5
99 150
1 100
100 301
2 5
150 250
2
0 720
720 1440
Output :
Case #1: CJC
Case #2: IMPOSSIBLE
Case #3: JCCJJ
Case #4: CC
Мой подход:
отсортировать значения задачи по времени начала или окончания и проверить, может ли она быть присвоена C или J. Если все задачи могут быть назначены, тогда все хорошее в противном случае невозможно.
Я пробовал сортировать по времени начала и времени окончания, но для обоих случаев получил WA.
, если кто-то может укажите, что мне не хватает в реализации, что qoulfd будет очень полезным.
Мой код:
#include<bits/stdc++.h>
using namespace std;
typedef struct task
{
int start_time;
int finish_time;
task()
{
this->start_time=0;
this->finish_time=0;
}
task(int start_time, int finish_time)
{
this->start_time=start_time;
this->finish_time=finish_time;
}
bool operator<(const task t)
{
return this->start_time<t.start_time;
}
}task;
int main()
{
int t;
cin>>t;
int a=1;
while(t--)
{
int n,st,ft;
cin>>n;
char res[1005];
int index = 0;
vector<task> task_list;
for(int i=0;i<n;i++)
{
cin>>st>>ft;
task t1(st,ft);
task_list.push_back(t1);
}
sort(task_list.begin(),task_list.end());
task j_task, c_task;
for(int i=0;i<n;i++)
{
if(task_list[i].start_time>=j_task.finish_time)
{
j_task = task_list[i];
res[index++] = 'J';
}
else if(task_list[i].start_time>=c_task.finish_time)
{
c_task = task_list[i];
res[index++] = 'C';
}
else
{
index = 0;
break;
}
}
if(index!=0)
{
res[index] = '\0';
cout<<"Case #"<<a++<<": "<<res<<endl;
}
else
{
cout<<"Case #"<<a++<<": "<<"IMPOSSIBLE"<<endl;
}
}
return 0;
}