Home » Interview coding problems/challenges

Parenting Partnering Returns - Google CodeJam 2020 Qualification Round Problem Solution

Parenting Partnering Returns: This problem has been featured in Google Codejam 2020 qualification round.
Submitted by Radib Kar, on August 14, 2020

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.

Constraints:

1 ≤ T ≤ 100.
0 ≤ Si< Ei  ≤ 24 × 60.
2 ≤ N ≤ 1000.

Example

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

Source: Parenting Partnering Returns

Explanation

Sample Case #1 is the one described in the problem statement. As mentioned above, there are other valid solutions, like JCJ and JCC.

In Sample Case #2, all three activities overlap with each other. Assigning them all would mean someone would end up with at least two overlapping activities, so there is no valid schedule.

In Sample Case #3, notice that Cameron ends an activity and starts another one at minute 100.

In Sample Case #4, any schedule would be valid. Specifically, it is OK for one partner to do all activities.

Solution

This is kind of job scheduling problem and thus firstly we need to sort the intervals based on starting time.

After sorting, we basically has two person to assign the jobs without overlapping. But since after sorting the position of the jobs will be changed so, we need to track their original indexes for final output.

WE have two person to assign jobs , Jaime as J and Cameron as C

We would declare two stacks namely Stack J and Stack C for them respectively.

Also, result will be our output which is a character array of length equal to number of jobs.

We will assign job based on their sorted order.

We will first try to assign job to J, if it's not possible then will try to assign job to C, if that's also not possible then it's impossible to assign jobs.

If job is possible to assign, we will push the job to the respective stack and we will mark the original index of the job with respective name ('C' or 'J' depending on which stack we assigned)

To keep track of original job index we create a structure like below:

class job{
    public:
    int index; //original index in input list
    int start; //start time  
    int end; //end time
}

Then sort the input list based on start time. For details refer to the comparator function in my code.

Let the sorted list be jobs with length n

1. Initialize two stacks as empty first
2. Initialize the character array of length n( n be number of jobs)
3. Push the first job in stack C and mark result[jobs[0].index] = 'C'

Remember jobs[0].index may not be 0 as we have sorted the original list and this will return the original index from the input. (this the purpose of the structure we created).

1. for(int i=1;i<n;i++)
       if  jobs[i].start>stack C top.end
           Push jobs[i] to stack C
           Mark result[jobs[i].index] as 'C'
       Else
           if  jobs[i].start>stack J top.end
               Push jobs[i] to stack j
               Mark result[jobs[i].index] as 'J'
           Else
               It's impossible to assign jobs ,so return "Impossible"
       end if-else
   End for
   

2. If it was possible to assign jobs, the result array has the final answer.

Dry run with example:

For the first example,

Number of jobs=3

Jobs are:
360 480
420 540
600 660

After sorting based on start time
360 480 ,index =0
420 540, index =1
600 660, index =2

It was pre-sorted basically

Now,
Assign job_0 to stack C and mark result[0]='C'  
For the next job we can't assign to stack c AS there's overlapping
Assign it to stack J and mark result[1]='J'
The last job can be assigned to stack C and thus final result will be "CJC"

C++ Implementation

#include <bits/stdc++.h>
using namespace std;

class job {
public:
    int index;
    int start;
    int end;
    job()
    {
        index = 0;
        start = 0;
        end = 0;
    }
};

bool mycomp(job a, job b)
{
    if (a.start < b.start)
        return true;
    else if (a.start > b.start)
        return false;
    else
        return (a.index < b.index);
}

int main()
{
    int t;
 
    cin >> t;
 
    for (int test_case = 1; test_case <= t; test_case++) {
        int n;
 
        cin >> n;
 
        vector<job> arr(n);
 
        int lstart, lend;
        for (int i = 0; i < n; i++) {
            cin >> lstart >> lend;
            arr[i].index = i;
            arr[i].start = lstart;
            arr[i].end = lend;
        }
        sort(arr.begin(), arr.end(), mycomp);

        stack<job> st1;
        stack<job> st2;
 
        char result[n];
        st1.push(arr[0]);
 
        result[arr[0].index] = 'C';
 
        bool flag = false;
        for (int i = 1; i < n; i++) {
            job pq = st1.top();
            if (arr[i].start < pq.end) {
                if (st2.empty()) {
                    st2.push(arr[i]);
                    result[arr[i].index] = 'J';
                }
                else {
                    job pv = st2.top();
                    if (arr[i].start < pv.end) {
                        flag = true;
                        break;
                    }
                    else {
                        st2.push(arr[i]);
                        result[arr[i].index] = 'J';
                    }
                }
            }
            else {
                st1.push(arr[i]);
                result[arr[i].index] = 'C';
            }
        }

        if (flag == true) {
            cout << "Case #" << test_case << ": "
                 << "IMPOSSIBLE" << endl;
        }
        else {
            string s = "";
            for (int i = 0; i < n; i++)
                s += string(1, result[i]);

            cout << "Case #" << test_case << ": " << s << endl;
        }
    }
    
    return 0;
}

Output

4
3
360 480
420 540
600 660
Case #1: CJC
3
0 1440
1 3
2 4
Case #2: IMPOSSIBLE
5
99 150
1 100
100 301
2 5
150 250
Case #3: JCCJJ
2
0 720
720 1440
Case #4: CC

---

Also tagged in: Google Interview Questions