## Google codejam 2020 parenting partnering returns solution

0
/
319

### Problem Statement

Cameron and Jamie’s kid is almost 3 years old! However, even though the child is more independent now, scheduling kid activities and domestic necessities is still a challenge for the couple. Cameron and Jamie have a list of**N**activities to take care of during the day. Each activity happens during a specified interval during the day. They need to assign each activity to one of them, so that neither of them is responsible for two activities that overlap. An activity that ends at time t is not considered to overlap with another activity that starts at time t. For example, suppose that Jamie and Cameron need to cover 3 activities: one running from 18:00 to 20:00, another from 19:00 to 21:00 and another from 22:00 to 23:00. One possibility would be for Jamie to cover the activity running from 19:00 to 21:00, with Cameron covering the other two. Another valid schedule would be for Cameron to cover the activity from 18:00 to 20:00 and Jamie to cover the other two. Notice that the first two activities overlap in the time between 19:00 and 20:00, so it is impossible to assign both of those activities to the same partner. Given the starting and ending times of each activity, find any schedule that does not require the same person to cover overlapping activities, or say that it is impossible.

**Input**

The first line of the input gives the number of test cases, **T**.

**T**test cases follow. Each test case starts with a line containing a single integer

**N**, the number of activities to assign. Then,

**N**more lines follow. The i-th of these lines (counting starting from 1) contains two integers

**S**

**i**and

**E**

**i**. The i-th activity starts exactly

**S**

**i**minutes after midnight and ends exactly

**E**

**i**minutes after midnight.

**Output**

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is IMPOSSIBLE if there is no valid schedule according to the above rules, or a string of exactly **N**characters otherwise. The i-th character in y must be C if the i-th activity is assigned to Cameron in your proposed schedule, and J if it is assigned to Jamie. If there are multiple solutions, you may output any one of them. (See “What if a test case has multiple correct solutions?” in the Competing section of the FAQ. This information about multiple solutions will not be explicitly stated in the remainder of the 2020 contest.)

**Limits**

Time limit: 20 seconds per test set.
Memory limit: 1GB.
1 ≤ **T**≤ 100. 0 ≤

**S**

**i**<

**E**

**i**≤ 24 × 60.

#### Test set 1 (Visible Verdict)

2 ≤**N**≤ 10.

#### Test set 2 (Visible Verdict)

2 ≤**N**≤ 1000.

**Sample**

Input | Output |

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 | Case #1: CJC Case #2: IMPOSSIBLE Case #3: JCCJJ Case #4: CC |

**C++ solution to this problem below:-**

#include <bits/stdc++.h> using namespace std; struct Interval { int start; int end; int index; }; bool compareInterval(Interval i1, Interval i2) { return (i1.start < i2.start); } int main() { int T, k = 1; cin >> T; while (T--) { int N, S, E, cameron, jamie; std::string output = ""; bool impossible = false; cin >> N; vector <Interval> array(N); for (int i = 1; i <= N; i++) { cin >> S >> E; array[i-1].start = S; array[i-1].end = E; array[i-1].index = i-1; } // sort the array in terms of increasing start times in the interval sort(array.begin(), array.end(), compareInterval); vector<string> schedule(N); schedule[array[0].index] = "C"; cameron = array[0].end; schedule[array[1].index] = "J"; jamie = array[1].end; for (int p = 2; p < N; p++) { if (cameron <= array[p].start) { cameron = array[p].end; schedule[array[p].index] = "C"; } else if (jamie <= array[p].start) { jamie = array[p].end; schedule[array[p].index] = "J"; } else { impossible = true; } } if (impossible) output = "IMPOSSIBLE"; else { for (int x = 0; x < N; ++x) output += schedule[x]; } cout << "Case #" << k << ": " << output << endl; //k is for printing the Case Number k++; } return 0; }

**Explanation**This is a basic scheduling problem where we want to check for overlaps in intervals for each of the persons Cameron and Jamie. We use the below approach

- Sort the input set of intervals in increasing order of start time. We use a struct Interval which has
**startTime**,**endTime**and**index**for saving the schedule map for the given input set of intervals

- Get user input (intervals) and push it into vector of struct
**Interval.**Once all input is read, sort the vector by**startTime**.

- Keep a schedule vector which will hold the output sequence of persons based on activity. Initialize the first 2 items of this schedule vector to
**Cameron**and**Jamie**or vice versa as the first 2 activities can be assigned to any of them in any order.

- Save the end time of each of the person’s activities as seen in variables
**cameron**and**jamie**for. Loop through the remaining set of intervals, compare the**itervative comparison****start****time**of each of the intervals with theof**end times****Cameron**and**Jamie**. If theof a particular person is**end time**the**less than**of the current activity (interval) being processed, assign it to the respective person, viz. Cameron or Jamie as applicable. If there is an overlap with both of the persons for a given activity, then that means that there is no valid schedule for the given interval set and set the impossible flag to**start time****TRUE**.

- Once we have processed all the intervals, output the sequence, by iterating through the schedule vector, appending each character in vector to an output string. Once all elements are processed, output the schedule string. If
is set to**impossible****flag**, output “**true****IMPOSSIBLE”**

**Try the above solution here:-***https://codingcompetitions.withgoogle.com/codejam/round/000000000019fd27/000000000020bdf9*Subscribe and follow Golibrary on Facebook and Linkedin to get all the updates.