In this problem i sorted the activity by their ending time. With this solution i got Wrong Answer 6 times. I got so much frustrated that i implemented this brute force solution & even it give me a wrong answer. Would you please point out my mistake.
PS: This is my first solution , which is also incorrect.
If you sort using starting time it will be solved even I faced same problem.
Google wants us to think why we are doing particular thing and not to copy paste the concepts.
Even I have not cleared the qualification round due to this problem even during the contest I also thought that why I am sorting using end time but I haven’t tried with start time during competition.
I solved it after competition.
there will definitely a test case that fails when we sort using end time which will be passed when we sort using start time .
When you solve easy question first time write concepts somewhere why you did it?
So that later you can check wether that is case in particular problem.
You can reference from my solution which got both the Test Sets correct, I’ve commented each and every line with explanation, hope that helps. solution
You could simply look at it was a standard graph coloring problem.
Every task is a node on a graph. There is an edge between two tasks if their timings overlap. Now you just have two check if the graph is bipartite.
i thought in this way also, but i got confused i.e consider activity A[1,11] , B[6,9] , C[1,6] then how would the graph will look like. Could you provide your solution with bipartite matching.
see…the thing is whenever tasks are being taken up by the C and J…they take it in increasing order of starting time… i mean if me and you decide to optimally do a set of tasks, we will start choosing from time 0.00 right and not 440 then 2 then 1200?
so we sort them based on the starting time. Now, suppose ending time of the previous task is larger than starting time of current task(overlap), so we give it to the other person. If there are 3 time intervals where there is overlap…return false(for this case I used an array and stored a maximum number of tasks at any interval of time between [0,1440])
this is my code
import java.io.;
import java.util.;
class Solution
{
public static void main(String args[])throws Exception
{
BufferedReader bu=new BufferedReader(new InputStreamReader(System.in));
int t=Integer.parseInt(bu.readLine()),v;
StringBuilder sb=new StringBuilder();
for(v=1;v<=t;v++)
{
int n=Integer.parseInt(bu.readLine());
int i,j,a[][]=new int[n][3],used[]=new int[n],check[]=new int[24*60+1];
char c[]=new char[n];
int flag=0;
for(i=0;i<n;i++)
{
String s[]=bu.readLine().split(" “);
a[i][0]=Integer.parseInt(s[0]);
a[i][1]=Integer.parseInt(s[1]);
a[i][2]=i;
for(j=a[i][0];j<a[i][1];j++)
{check[j]++;
if(check[j]>2) {flag=1; break;}}
//if(flag==1) break;
}
if(flag==1) {sb.append(“Case #”+v+”: IMPOSSIBLE\n"); continue;}
Arrays.sort(a,new Comparator<int[]>()
{
public int compare(int entry1[],int entry2[])
{
if(entry1[0]>=entry2[0]) return 1;
else return -1;
}
});
int last=a[0][1];
c[a[0][2]]=‘J’;
for(i=1;i<n;i++)
{
if(a[i][0]>=last) {c[a[i][2]]=‘J’; last=a[i][1];}
else c[a[i][2]]=‘C’;
}
sb.append(“Case #”+v+“: “);
for(i=0;i<n;i++)
sb.append(c[i]);
sb.append(”\n”);
}
System.out.print(sb);
}
}
I also maintained two arrays [cam] & [jam] for similar thing
My Python Solution [Both Test Case Pass] 
def f(grid):
hmp = {}
for i in range(len(grid)): #time slot position in the orignal array
g = grid[i]
if (g[0],g[1]) not in hmp:
hmp[(g[0],g[1])] = []
hmp[(g[0],g[1])].append(i)
if len(hmp[(g[0],g[1])]) > 2:
return "IMPOSSIBLE"
schedule = sorted(grid)
j, c = -float('inf'), -float('inf') #to record the activity end time
output = [None] * len(schedule)
for i in range(len(schedule)):
curr = schedule[i]
if j <= curr[0]:
if output[hmp[(curr[0], curr[1])][0]] == None:
output[hmp[(curr[0], curr[1])][0]] = "J"
else:
output[hmp[(curr[0], curr[1])][1]] = "J"
j = curr[1]
elif c <= curr[0]:
if output[hmp[(curr[0], curr[1])][0]] == None:
output[hmp[(curr[0], curr[1])][0]] = "C"
else:
output[hmp[(curr[0], curr[1])][1]] = "C"
c = curr[1]
else: #j > curr[0] and c > curr[0]
return "IMPOSSIBLE"
return ''.join(output)
cnt = int(input())
for i in range(1, cnt + 1): # go through all the cases
N = int(input())
grid = []
for j in range(N):
grid.append(str(input()).split(" "))
for r in range(len(grid)):
for c in range(len(grid[0])):
grid[r][c] = int(grid[r][c])
res = f(grid)
print("Case #{}: {}".format(i, res))Actually me too solved the problem but i need why sorting by ending time solution fails.
You were supposed to sort them according to their start time, get the solution and then sort the array according to original indexes and then give the answer(The validity for this statement you can check by seeing the third test case In sample case 1). I used a structure for this purpose.
Hope this helps!
but my solution (sorting by end) works fine for that test case you can check it.
that us just because of the input pattern. If I give you an input which is unsorted completely(by end and by start), you will get a wrong answer
yeah , can you provide such testcase.
Hi, I sovled this question by sorting by the finish time. Do have a look at my code.
p.ip.fi/MejG
Sorted according to finish time and added index of each job to a vector<pair<pair<int,int>,int>>
Initialised two timekeeping variables Cfree and Jfree to keep track of when each parent is getting free from previous job.
Assigining First Job to C. (you can give it to J also doesnt matter)
For next job, trying to assign it to previous person, if that person is busy, try to assign it to other person, if that person is also busy, return Impossible.
Do have a look at my code, any suggestions to improve my clunky code would be appreciated.
Thanks 
I just want to ask one question hello_hell why u sort using activity ending time not using activity start time?
May be I have not conveyed in polite, better manner but originally this is the reason.
I also mentioned that i thought this as a Exchange Argument problem.
ok hello_hell.
Can you tell me that when should your code print “Something is Wrong” ?
