Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг 4.80/5: Рейтинг темы: голосов - 5, средняя оценка - 4.80
Fixer_84
1344 / 842 / 770
Регистрация: 30.04.2016
Сообщений: 2,829
1

Задача Прием у директора

10.05.2017, 20:08. Просмотров 930. Ответов 20
Метки нет (Все метки)

Здравствуйте, уважаемые пользователи этого замечательного форума!

Написал несложную программу на работу со структурой (E-olymp №13), но в последнем тесте - неправильный ответ. Очень надеюсь на вашу помощь! Помогите, пожалуйста, найти ошибку.

Условие задачи:

Прием у директора

Секретарь общеобразовательного учреждения Марта Георгиевна ежедневно начинала свой рабочий день с претензий к директору:

Вот Вы, Иван Иванович, заместителю по учебной части программу для составления расписания уже приобрели. А что мне делать? Ведь мне нужно согласно Ваших требований составить график приема посетителей, а программу для планирования работы администрации Вы мне не приобрели...
Попробуйте помочь секретарю в ее роботе. Для этого вам нужно организовать прием посетителей на основании пожеланий, сделанных ими в соответствующей книге у секретаря.

Прием двух посетителей одновременно запрещен. В момент завершения приема одного посетителя может начаться прием другого - они встретились в дверях кабинета.

Входные данные:

В первой строке число n (n ≤ 1000) - количество посетителей, записавшихся на прием. В последующих n строках по два числа T1i - время начала встречи с директором и через пробел T2i - время ее завершения в формате hh:mm. Известно, что ремя задано в течении одних суток, все T2i ≥ T1i.

Выходные данные:

Максимальное количество посетителей, которое сможет принять директор учреждения на протяжении рабочего дня.

Входные данные #1:
4
09:10 13:05
14:25 14:30
14:20 15:15
15:00 17:00

Выходные данные #1:
3

Мой код:

C++
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <iostream>
#include <fstream>
#include <string>
#include <algorithm>
 
using namespace std;
 
int TimeIntoMin(string s) //Переводим время в часах и минутах в минуты
{
    return atoi(s.substr(0, 2).c_str()) * 60 + atoi(s.substr(3, 2).c_str());
}
 
int main()
{
    ifstream fin("input.txt");
    ofstream fout("output.txt");
    int N, k;
    fin >> N; //Количество посетителей, записавшихся на прием
    struct Time
    {
        string begin;
        string end;
    } A[N];
    int* B = new int[N];
    int* E = new int[N];
    for (int i = 0; i < N; i++)
    {
        fin >> A[i].begin >> A[i].end; //Считываем время начала и конца приема в структуру
    }
    sort(A, A + N, [](const Time& a, const Time& b) //Сортируем структуру по времени начала приема
        {
            return a.begin < b.begin;
        });
    for (int i = 0; i < N; i++)
    {
        B[i] = TimeIntoMin(A[i].begin); //Массив полных минут начала приема
        E[i] = TimeIntoMin(A[i].end); //Массив полных минут конца приема
    }
    k = 0;
    for (int i = 0; i < N - 1; i++)
    {
        if (B[i+1] >= E[i]) //Условие состоявшегося приема (интервалы конца и начала приема отсортированы по началу приема)
            k++;
    }
    fout << ++k << endl;
    fin.close();
    fout.close();
    delete[] B;
    delete[] E;
    system("pause");
    return 0;
}
Добавлено через 26 минут
Может быть, я не учитываю 00:00. Это время при сортировке в начало (а не конец) списка уходит.

Добавлено через 41 минуту
Пробовал сдвигать массивы на B[N] и E[N] на один элемент влево (чтобы перенести 00:00 в конец) и добавлял в этом случае к счетчику единицу. Все равно в последнем тесте - неправильный ответ. И N = 0 также учитывал...В чем может быть ошибка? Вот мой последний код:

C++
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <iostream>
#include <fstream>
#include <string>
#include <algorithm>
 
using namespace std;
 
int TimeIntoMin(string s) //Переводим время в часах и минутах в минуты
{
    return atoi(s.substr(0, 2).c_str()) * 60 + atoi(s.substr(3, 2).c_str());
}
 
int main()
{
    ifstream fin("input.txt");
    ofstream fout("output.txt");
    int N, k, x, y;
    fin >> N; //Количество посетителей, записавшихся на прием
    struct Time
    {
        string begin;
        string end;
    } A[N];
    int* B = new int[N];
    int* E = new int[N];
    for (int i = 0; i < N; i++)
    {
        fin >> A[i].begin >> A[i].end; //Считываем время начала и конца приема в структуру
    }
    sort(A, A + N, [](const Time& a, const Time& b) //Сортируем структуру по времени начала приема
        {
            return a.begin < b.begin;
        });
    for (int i = 0; i < N; i++)
    {
        B[i] = TimeIntoMin(A[i].begin); //Массив полных минут начала приема
        E[i] = TimeIntoMin(A[i].end); //Массив полных минут конца приема
        //cout << B[i] << " " << E[i] << endl;
    }
    k = 0;
    if (B[0] == 0)
    {
        x = B[0];
        y = E[0];
        for (int i = 0; i < N - 1; i++) //Сдвигаем элементы влево и увеличиваем счетчик на единицу (если присутствует 00:00)
        {                                 
            B[i] = B[i+1];
            E[i] = E[i+1];
        }
        B[N-1] = x;
        E[N-1] = y;
        k++;
    }
    for (int i = 0; i < N - 1; i++)
    {
        if (B[i+1] >= E[i]) //Условие состоявшегося приема (интервалы конца и начала приема
            //отсортированы по началу приема)
            k++;
    }
    if (N == 0)
        fout << 0 << endl;
    else
        fout << ++k << endl;
    fin.close();
    fout.close();
    delete[] B;
    delete[] E;
    system("pause");
    return 0;
}
Добавлено через 38 минут
Еще не рассматривал такой случай.
Вот часть неправильно отсортированной структуры:

00:01 17:00
00:01 14:00
00:01 15:00
00:01 17:05

16:00 16:15 - в этом случае важно какой из четырех интервалов сверху ближе находится к этому времени. Если 17:00 или 17:05 - счетчик не увеличивается. А если 14:00 или 15:00 то увеличивается. Кажется дело в этом. Попробую исправить.
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
10.05.2017, 20:08
Ответы с готовыми решениями:

Асинхронные сокеты: Как организовать разделение на прием сообщений и прием файлов
Изучив синхронные сокеты, перешел к изучению асинхронных. Столкнулся вот с чем, как, используя...

Google меняет директора
Понятно, что для большинства из нас не важно, кто в гугле главный, оптимизаторов больше волнуют...

Директора школы судили за XP
По данным одного из моих знакомых работающих в обасти новостей: Директора школы судили за...

Формирование отчета, два директора
Добрый день! Имеется база данных по Компаниям. С помощью запросов и отчета формирую Карточку...

Какой монитор у вашего директора?
Требуется создать сайт, ориентированный исключительно на директоров и их заместителей. При этом в...

20
GoldenId
131 / 130 / 64
Регистрация: 11.11.2010
Сообщений: 771
Записей в блоге: 14
Завершенные тесты: 1
10.05.2017, 21:03 2
Там если кликнуть на Показать классификацию задачи, то написана подсказка: жадный алгоритм. Если на каком-то шаге построения расписания, у Вас оно оканчивается на времени t, то на следующем шаге следует взять любого посетителя, начальное время которого >= t, а конечное - минимально.

Вот моё...
C++
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <algorithm>
#include <fstream>
#include <iostream>
#include <vector>
 
int main()
{
    std::ifstream is( "input.txt" );
    int n;
    is >> n;
    std::vector<std::pair<int, int>> vs( n + 1 );
    vs[0].first = vs[0].second = -1;
    for( int i = 1; i < n + 1; i++ )
    {
        int h, m;
        is >> h;
        is.ignore();
        is >> m;
        vs[i].first = h*60 + m;
        is >> h;
        is.ignore();
        is >> m;
        vs[i].second = h*60 + m;
    }
    is.close();
    std::sort( vs.begin(), vs.end(), [] ( std::pair<int, int>/*auto*/ p1, std::pair<int, int>/*auto*/ p2 ) { return p1.first < p2.first; } );
    int curr = 0, next, min;
    int count = 0;
    while( true )
    {
        for( next = curr + 1; next < n + 1; next++ )
            if( vs[next].first >= vs[curr].second )
        {
            min = next;
            break;
        }
        if( next == n + 1 )
            break;
        count++;
        for( ; next < n + 1; next++ )
            if( vs[next].first >= vs[curr].second && vs[next].second < vs[min].second )
                min = next;
        curr = min;
    }
    std::ofstream os( "output.txt" );
    os << count;
    os.close();
    return 0;
}

Задача Прием у директора
2
Fixer_84
1344 / 842 / 770
Регистрация: 30.04.2016
Сообщений: 2,829
10.05.2017, 21:18  [ТС] 3
К сожалению, все случаи выше, включая последний никаких результатов не дали. По прежнему один неправильный ответ в последнем тесте.

Вот последний код. Все, кажется, работает правильно. И, все-таки, я чего-то не досмотрел...Даже последняя возможная ошибка рассмотрена:

C++
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <iostream>
#include <fstream>
#include <string>
#include <algorithm>
 
using namespace std;
 
int F(string s)
{
    return atoi(s.substr(0, 2).c_str()) * 60 + atoi(s.substr(3, 2).c_str());
}
 
int main()
{
    ifstream fin("input.txt");
    ofstream fout("output.txt");
    int N, k, x, y;
    fin >> N;
    struct Time
    {
        string begin;
        string end;
    } A[N];
    int* B = new int[N];
    int* E = new int[N];
    for (int i = 0; i < N; i++)
    {
        fin >> A[i].begin >> A[i].end; 
    }
    for (int i = 0; i < N; i++) 
    {
    for (int j = N - 1; j > i; j--)
    {
    if (F(A[j-1].begin) + F(A[j-1].end) < F(A[j].begin) + F(A[j].end))
    {
    swap(A[j-1].begin, A[j].begin);
    swap(A[j-1].end, A[j].end);
    }
    }
    } 
    sort(A, A + N, [](const Time& a, const Time& b) 
        {
            return a.begin < b.begin;
        });
    for (int i = 0; i < N; i++)
    {
        B[i] = F(A[i].begin); 
        E[i] = F(A[i].end); 
        //cout << A[i].begin << " " << A[i].end << endl; //Здесь отсортированная структура
    }
    k = 0;
    for (int i = 0; i < N - 1; i++)
    {
        if (B[i+1] >= E[i]) 
            k++;
    }
    fout << ++k << endl;
    fin.close();
    fout.close();
    delete[] B;
    delete[] E;
    system("pause");
    return 0;
}
Для такого набора:

10
09:10 13:05
14:00 14:30
14:00 16:55
15:00 17:05
15:00 17:02
14:00 18:00
15:00 17:00
18:00 17:07
14:00 17:02
15:00 17:10


Выдает:

09:10 13:05
14:00 18:00
14:00 17:02
14:00 16:55
14:00 14:30
15:00 17:10
15:00 17:05
15:00 17:02
15:00 17:00
18:00 17:07
k = 4


Что я мог не учесть?

Добавлено через 9 минут
GoldenId, Спасибо вам! Я, вроде бы, так и сделал. Даже когда несколько расписаний с одним и тем же временем учел, как рассмотрено выше. Вы можете сказать, что в моем коде может быть не так?
0
GoldenId
131 / 130 / 64
Регистрация: 11.11.2010
Сообщений: 771
Записей в блоге: 14
Завершенные тесты: 1
10.05.2017, 21:30 4
Цитата Сообщение от Fixer_84 Посмотреть сообщение
18:00 17:07
Такого по условию задачи быть не может.
0
10.05.2017, 21:30
Fixer_84
1344 / 842 / 770
Регистрация: 30.04.2016
Сообщений: 2,829
10.05.2017, 21:45  [ТС] 5
Да, это опечатка. Я, конечно, имел ввиду T2i >= T1i (как сказано в условии).
0
GoldenId
131 / 130 / 64
Регистрация: 11.11.2010
Сообщений: 771
Записей в блоге: 14
Завершенные тесты: 1
10.05.2017, 21:52 6
Такие входные данные:
Код
0
0
Fixer_84
1344 / 842 / 770
Регистрация: 30.04.2016
Сообщений: 2,829
10.05.2017, 22:03  [ТС] 7
При нуле будет ноль - я это уже проверял.
0
GoldenId
131 / 130 / 64
Регистрация: 11.11.2010
Сообщений: 771
Записей в блоге: 14
Завершенные тесты: 1
10.05.2017, 22:10 8
Вот это при нуле выдаёт единицу.
C++
1
2
3
4
5
6
7
    k = 0;
    for (int i = 0; i < N - 1; i++)
    {
        if (B[i+1] >= E[i]) 
            k++;
    }
    fout << ++k << endl;
0
Fixer_84
1344 / 842 / 770
Регистрация: 30.04.2016
Сообщений: 2,829
10.05.2017, 22:27  [ТС] 9
Я имел ввиду, что уже отправлял с исправленным нулем, а в последнем тесте все равно неправильный ответ. Я и время 00:00 проверял...Кстати. вы учитывали это время в своем решении?

Вот код:

C++
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <iostream>
#include <fstream>
#include <string>
#include <algorithm>
 
using namespace std;
 
int F(string s)
{
    return atoi(s.substr(0, 2).c_str()) * 60 + atoi(s.substr(3, 2).c_str());
}
 
int main()
{
    ifstream fin("input.txt");
    ofstream fout("output.txt");
    int N, k, x, y;
    fin >> N;
    struct Time
    {
        string begin;
        string end;
    } A[N];
    int* B = new int[N];
    int* E = new int[N];
    for (int i = 0; i < N; i++)
    {
        fin >> A[i].begin >> A[i].end;
    }
    for (int i = 0; i < N; i++)
    {
        for (int j = N - 1; j > i; j--)
        {
            if (F(A[j-1].begin) + F(A[j-1].end) < F(A[j].begin) + F(A[j].end))
            {
                swap(A[j-1].begin, A[j].begin);
                swap(A[j-1].end, A[j].end);
            }
        }
    }
    sort(A, A + N, [](const Time& a, const Time& b)
        {
            return a.begin < b.begin;
        });
    for (int i = 0; i < N; i++)
    {
        B[i] = F(A[i].begin);
        E[i] = F(A[i].end);
    }
    k = 0;
    for (int i = 0; i < N - 1; i++)
    {
        if (B[i+1] >= E[i])
            k++;
    }
    if (N == 0)
        fout << 0 << endl;
    else
        fout << ++k << endl;
    fin.close();
    fout.close();
    delete[] B;
    delete[] E;
    system("pause");
    return 0;
}
0
GoldenId
131 / 130 / 64
Регистрация: 11.11.2010
Сообщений: 771
Записей в блоге: 14
Завершенные тесты: 1
10.05.2017, 22:43 10
Код
3
11:00 13:00
12:00 14:00
13:00 15:00

Код
1
Нельзя так:
C++
1
2
3
4
5
    for (int i = 0; i < N - 1; i++)
    {
        if (B[i+1] >= E[i])
            k++;
    }
Добавлено через 1 минуту
Эта заплата это подтверждает
C++
1
2
if (N == 0)
* * * * fout << 0 << endl;
1
Fixer_84
1344 / 842 / 770
Регистрация: 30.04.2016
Сообщений: 2,829
11.05.2017, 19:46  [ТС] 11
GoldenId, Да, этот случай я не рассматривал. Попробую учесть и это. Спасибо!

Добавлено через 20 часов 45 минут
GoldenId, извините, я не совсем понял. Вчера уже поздно было, я ответил невпопад. Для этого:

C++
1
2
3
4
3
11:00 13:00
12:00 14:00
13:00 15:00
программа выдает единицу (N = 3 и мы выбираем 1 интервал (11:00 13:00)). Что именно не так?
0
GoldenId
131 / 130 / 64
Регистрация: 11.11.2010
Сообщений: 771
Записей в блоге: 14
Завершенные тесты: 1
11.05.2017, 20:10 12
Ну у Вас программа Выдаёт единицу, тогда как максимально можно принять двух человек: 11:00-13:00 и 13:00-15:00.
1
Fixer_84
1344 / 842 / 770
Регистрация: 30.04.2016
Сообщений: 2,829
11.05.2017, 20:42  [ТС] 13
Да, вы правы. Я неправильно сортировал структуру, думая, что оптимальный путь - это упорядочить все по времени начала приема. Буду переделывать программу. Спасибо вам большое!
0
GoldenId
131 / 130 / 64
Регистрация: 11.11.2010
Сообщений: 771
Записей в блоге: 14
Завершенные тесты: 1
11.05.2017, 20:51 14
Их и нужно упорядочивать по времени начала приёма (во всяком случае этот способ приводит к оптимальному решению), просто в качестве следующего в решении нужно выбирать не следующий в таблице, при
C++
1
B[i+1] >= E[i]
,
а дальнейший в таблице при
C++
1
B[j] >= E[i]
с минимальным
C++
1
E[j]
1
Fixer_84
1344 / 842 / 770
Регистрация: 30.04.2016
Сообщений: 2,829
11.05.2017, 21:43  [ТС] 15
GoldenId, сделал так:

C++
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <iostream>
#include <fstream>
#include <string>
#include <algorithm>
#include <climits>
 
using namespace std;
 
int F(string s)
{
    return atoi(s.substr(0, 2).c_str()) * 60 + atoi(s.substr(3, 2).c_str());
}
 
int main()
{
    ifstream fin("input.txt");
    ofstream fout("output.txt");
    int N, k, p, min;
    fin >> N;
    struct Time
    {
        string begin;
        string end;
    } A[N];
    int* B = new int[N];
    int* E = new int[N];
    for (int i = 0; i < N; i++)
    {
        fin >> A[i].begin >> A[i].end;
    }
    sort(A, A + N, [](const Time& a, const Time& b)
        {
            return a.begin < b.begin;
        });
    for (int i = 0; i < N; i++)
    {
        B[i] = F(A[i].begin);
        E[i] = F(A[i].end);
        //cout << A[i].begin << " " << A[i].end << endl;
    }
    k = p = 0;
    for (int i = p; i < N; i++)
    {
    min = INT_MAX;
    for (int j = i + 1; j < N; j++)
    {
    if ((B[j] >= E[i]) && (E[j] < min)) 
    {
    min = E[j];
    p = j;
    k++;
    break;
    }
    }
    }
    if (N == 0)
        fout << 0 << endl;
    else
        fout << ++k << endl;
    fin.close();
    fout.close();
    delete[] B;
    delete[] E;
    system("pause");
    return 0;
}
Но почему-то для:

5
11:00 13:00
12:00 14:00
13:00 15:00
15:00 17:00
15:00 16:00


выдает 4 вместо 3. Я ведь вас правильно понял?
0
GoldenId
131 / 130 / 64
Регистрация: 11.11.2010
Сообщений: 771
Записей в блоге: 14
Завершенные тесты: 1
11.05.2017, 22:04 16
У меня получилось два вложенных цикла внутри объемлющего (первый - для первой установки min, второй - для нахождения точного минимума):
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
    std::sort( vs.begin(), vs.end(), [] ( std::pair<int, int>/*auto*/ p1, std::pair<int, int>/*auto*/ p2 ) { return p1.first < p2.first; } );
    int curr = 0, next, min;
    int count = 0;
    while( true )
    {
        for( next = curr + 1; next < n + 1; next++ )
            if( vs[next].first >= vs[curr].second )
        {
            min = next;
            break;
        }
        if( next == n + 1 )
            break;
        count++;
        for( ; next < n + 1; next++ )
            if( vs[next].first >= vs[curr].second && vs[next].second < vs[min].second )
                min = next;
        curr = min;
    }
Я тоже пробовал через min = INT_MAX, но у меня не получилось. Может, мозгов не хватило. У Вас в
C++
1
2
3
4
5
6
7
    if ((B[j] >= E[i]) && (E[j] < min)) 
    {
    min = E[j];
    p = j;
    k++;
    break;
    }
break не даёт для i найти посетителя с минимальным временем окончания, а прерывает цикл на первом совпадении.
1
Fixer_84
1344 / 842 / 770
Регистрация: 30.04.2016
Сообщений: 2,829
11.05.2017, 22:35  [ТС] 17
Извините, не совсем понимаю. Я пробегаю для i = p (изначально p = 0) по всем j (j = i + 1) и как только B[j] >= E[i] и E[j] < min (то есть, E[j] - минимально) я увеличиваю счетчик на 1, присваиваю i - номер строки на которой я остановился (через p) и выхожу из внутреннего цикла. Далее начинаю проход с i = p (то есть, оттуда, где я остановился до этого и снова ищу как в самом начале, запоминаю где остановился, увеличиваю счетчик и т.д.)

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
k = p = 0;
for (int i = p; i < N; i++)
{
min = INT_MAX;
for (int j = i + 1; j < N; j++)
{
if ((B[j] >= E[i]) && (E[j] < min)) 
{
min = E[j];
p = j;
k++;
break;
}
}
}
Добавлено через 14 минут
Да, сейчас тестирую программу. Там с i и выводом p что-то не так...Буду думать как исправить.
0
GoldenId
131 / 130 / 64
Регистрация: 11.11.2010
Сообщений: 771
Записей в блоге: 14
Завершенные тесты: 1
11.05.2017, 22:41 18
Цитата Сообщение от Fixer_84 Посмотреть сообщение
выхожу из внутреннего цикла.
Здесь это неверно.
Т.к. Вы делаете
C++
1
min = INT_MAX;
то выражение
C++
1
(E[j] < min)
в условии фактически будет всегда истинно и ничего отсекать не будет.

Добавлено через 3 минуты
Ещё раз обращаю Ваше внимание, что например у меня в решении два внутренних цикла: один для установки первого значения min, второй для поиска точного его значения (второй можно оптимизировать, чтобы не идти каждый раз до самого конца таблицы).
p - лишняя переменная у Вас. При выходе из внутреннего цикла достаточно сделать
C++
1
i = j;
1
Fixer_84
1344 / 842 / 770
Регистрация: 30.04.2016
Сообщений: 2,829
12.05.2017, 19:58  [ТС] 19
GoldenId, здравствуйте! В конечном итоге, получилось обойтись без поиска минимумов. Вот мое решение, если вам интересно. Все тесты также пройдены

C++
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <iostream>
#include <fstream>
#include <string>
#include <algorithm>
 
using namespace std;
 
int F(string s)
{
    return atoi(s.substr(0, 2).c_str()) * 60 + atoi(s.substr(3, 2).c_str());
}
 
int main()
{
    ifstream fin("input.txt");
    ofstream fout("output.txt");
    int N, k, tmp;
    fin >> N;
    struct Time
    {
        string begin;
        string end;
    } A[N];
    int* B = new int[N];
    int* E = new int[N];
    for (int i = 0; i < N; i++)
    {
        fin >> A[i].begin >> A[i].end;
    }
    sort(A, A + N, [](const Time& a, const Time& b)
        {
            return a.begin < b.begin;
        });
    for (int i = 0; i < N; i++)
    {
        B[i] = F(A[i].begin);
        E[i] = F(A[i].end);
    }
    tmp = k = 0;
    for (int i = 1; i < N; i++)
    {
        for (int j = tmp; j < N; j++)
        {
            if (B[i] >= E[j])
            {
                k++;
                tmp = i;
                break;
            }
        }
    }
    fout << ++k << endl;
    fin.close();
    fout.close();
    delete[] B;
    delete[] E;
    system("pause");
    return 0;
}
Добавлено через 1 минуту
P.S. Я в предыдущих своих постах перепутал массивы местами...Отсюда и куча непонятных вопросов. Еще раз спасибо вам за помощь и поддержку.
0
GoldenId
131 / 130 / 64
Регистрация: 11.11.2010
Сообщений: 771
Записей в блоге: 14
Завершенные тесты: 1
13.05.2017, 19:24 20
Вы меня благодарите, а я Вам - при N = 0, ответ 1.
0
13.05.2017, 19:24
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
13.05.2017, 19:24

Сколькими способами можно выбрать директора
Здравствуйте . Сколькими способами можно выбрать директора, его заместителя и инженера из 18 человек

Удаленная работа для коммерческого директора
Корпорация специализируется и подготавливает менеджеров высшего звена для следующих web-бизнес...

СРОЧНО! как замучить директора школы??
СРОЧНО! как замучить директора школы?? :D нужно!!!


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru