Valid schedule · Coding Gym

Solutions

This is a problem on intervals. A brute force solution would involve checking every pair of talks to see if they overlap. We can iterate through each talk and compare it with every other talk. If any two talks overlap, the schedule is invalid. Two talks overlap if one starts before the other ends and vice versa. This results in a nested loop where each talk is compared against all others, leading to a quadratic time complexity.

A more efficient solution consists in sorting the input by their start time, and then checking if any interval overlaps in a single pass. This is as costly as the sorting algorithm that - in this case - is \(O(N \cdot logN)\).

Here is a C++ solution - we use a vector<pair<int, int>> to store the intervals that is a common and simple representation:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


int n, i, j;
cin >> n;
vector<pair<int, int>> talks;
while (n--)
{
    cin >> i >> j;
    talks.emplace_back(i, j);
}

sort(begin(talks), end(talks));

bool conflict = false;
for (size_t i=1; i<!conflict && talks.size(); ++i)
{
    if (talks[i].first < talks[i - 1].second)
    {
        conflict = true;
    }
}

cout << (conflict ? "KO" : "OK");

We can replace the for loop with the standard algorithm adjacent_find, which effectively finds two adjacent intervals that exhibit a specific property, such as overlapping:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


int n, i, j;
cin >> n;
vector<pair<int, int>> talks;
while (n--)
{
    cin >> i >> j;
    talks.emplace_back(i, j);
}

sort(begin(talks), end(talks));

cout << (end(talks) == adjacent_find(begin(talks), end(talks), [](const auto& i1, const auto& i2){
        return i1.second > i2.first;
    }) ? "OK" : "KO");

The same solution in Python:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


from itertools import pairwise

n = int(input())
talks = [tuple(map(int, input().split())) for _ in range(n)]

talks.sort()

if all(end <= next_start for (start, end), (next_start, _) in pairwise(talks)):
    print("OK")
else:
    print("KO")

intervals