Problem: CodeChef: Practical coding for everyone
My solution: CodeChef: Practical coding for everyone
Where is the mistake?
int main()
{ int i,n,max=0,c=0;
scanf("%d",&n);
int a[n],b[n];
for(i=0;i<n;i++)
{ scanf("%d%d",&a[i],&b[i]);
if(a[i]>max)
{ max=a[i];
}
}
for(i=0;i<n;i++)
{ if(b[i]>max)
{ c++;
}
}
printf("%d",c);
return 0;
}
This is your code.
what you have done is, after the first for loop (which also takes the input) is done, you will have the time t(m) where it is the final time that a person came in.
So let’s consider test case given by them.
5
1 7
2 4
6 9
3 8
5 10
Now the first loop will make max=6. time t0= 6 is the final time after which nobody entered. Now the second loop will count how many people exit the venue after the final person came in.
Now consider this test case:
10
1 10
2 9
3 8
4 7
5 6
11 17
12 14
16 19
13 18
15 20
Now clearly, your program will store max=16. Now with second loop, the people who go out after t=16 are: (serial nos.) 6,8,9,10.
But if you see people 1-5, they all belong to an overlapping time interval. Whereas your program doesn’t consider this case.
You have made an assumption here that the longest sequence of people being present at the value is the set of people that leaves the venue last.
You haven’t considered the fact that a set of people larger than the final set can enter and exit without any overlap with the max t0 set.
What you need to do: First think on the problem that such set can exist at any t0 time not just at end.
Store the values of in and out and find out maximum no of people that are there at one time.