Hi Aabhas! Sorting by start time allows us to focus on end times only. When we sort by start time, we can assign activities to Cameron and Jamie in any fashion we choose provided that the start time of the next activity is on or after the end time of the last activity that we assigned to him or her. A simpler example:
Hey, Cameron, can you take this 1-5? Sure! How about this 2-4? No, sorry. What about 5-7? Sure! When determining if we can or cannot take an activity, what we are doing is simply checking the 5 in 1-5 against the 2 in 2-4, and the 5 in 1-5 against the 5 in 5-7. Easy! Now let's mix it up... Hey, Cameron, can you take this 2-4? Sure! How about this 1-5? ... The output will end up looking the same, but the means in which we get there are a bit more intensive than before. When deciding if we can take the 1-5, we first need to decide if a 1 start time is okay, then we need to determine if a 5 end time is okay. With two activities, the check is relatively simple. With 1000 activities, the check is a bit more challenging as we would need to search our schedule to find the 1-5 interval and evaluate end times and start times, and vice versa. Now, when it comes to output, yes, we must give it in the same order in which it was received. When we are reading the input, we can index each event: the first event is 1, the second event is 2, and so on. When we sort, indices stay with the events regardless of where they end up after we have sorted the activities by start time so that, when we have assigned each activity to a partner, we can once again sort on indices. Now, activities are in the proper order, and each activity has an assignment. Does this answer your question? Best, Matt On Tuesday, April 7, 2020 at 12:56:02 PM UTC-4, AC wrote: > > Hi Bhavesh, > > Do we know why are we trying to sort the start time. > Since we do have to put the output in same order as we received it. > Is this a tie breaker condition for multiple solutions? > Can u share the edge cases for this. > > Thanks, > > On Tue, Apr 7, 2020 at 8:51 AM Bhavesh Kumar <[email protected] > <javascript:>> wrote: > >> Yes, I solved in Python. Idea is simple, maintain a list of tuples. Each >> tuple will have three values (start_time, end_time, index). now sort the >> list based on first value. Checkout the code below. >> >> for t in range(int(input())): >> N = int(input()) >> A = [] >> for i in range(N): >> s, e = map(int, input().split()) >> A.append((s, e, i)) >> >> A.sort() >> ans = ['X'] * N >> C, J = None, None >> for x in A: >> if C is not None: >> if C[1] <= x[0]: >> C = None >> >> if J is not None: >> if J[1] <= x[0]: >> J = None >> >> if C is None: >> C = x >> ans[x[2]] = "C" >> >> elif J is None: >> J = x >> ans[x[2]] = "J" >> >> else: >> ans = "IMPOSSIBLE" >> break >> >> >> if 'X' in ans: >> ans = "IMPOSSIBLE" >> >> if isinstance(ans, list): >> ans = "".join(ans) >> >> print("Case #{}: {}".format(t+1, ans)) >> >> >> >> >> >> >> >> On Tuesday, 7 April 2020 06:20:28 UTC+5:30, Martin Seeler wrote: >>> >>> I'm asking to keep my sanity: Did anyone solve this problem with Python? >>> I can't find these tricky edge cases where my code fails, all variations >>> I try on my machine seem to work just fine. Still CodeJam Environment says >>> *WA*. >>> >>> If there is someone who solved it in python, then I know I'm missing >>> some cases. Otherwise I start to question the environment :D >>> >>> Thanks and have a nice day everyone >>> >> -- >> You received this message because you are subscribed to the Google Groups >> "Google Code Jam" group. >> To unsubscribe from this group and stop receiving emails from it, send an >> email to [email protected] <javascript:>. >> To view this discussion on the web visit >> https://groups.google.com/d/msgid/google-code/034a5111-e44e-4a02-8f8b-7d8791e89a7a%40googlegroups.com >> >> <https://groups.google.com/d/msgid/google-code/034a5111-e44e-4a02-8f8b-7d8791e89a7a%40googlegroups.com?utm_medium=email&utm_source=footer> >> . >> > -- > Cheers! > Aabhas > > -- You received this message because you are subscribed to the Google Groups "Google Code Jam" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To view this discussion on the web visit https://groups.google.com/d/msgid/google-code/41f69fc4-91e9-426d-845b-baa445981239%40googlegroups.com.
