Hi all,
As we have seen the solution for this problem is to greedily assign the
task after sorting the *start time *of the activities. But I was thinking
sorting by the *end time *should also bring the correct result.
Nevertheless, I got WA for this approach. My code is as below
import java.util.*;
>
> import java.lang.*;
>
> import java.io.*;
>
>
>> class Solution
>
> {
>
> public static void main (String[] args) throws java.lang.Exception
>
> {
>
> Scanner scan = new Scanner(System.in);
>
> int totalTests = scan.nextInt();
>
> for(int test = 1; test<=totalTests; test++){
>
> int activities = scan.nextInt();
>
> char[] plannedSchedule = new char[activities];
>
> List<Integer> startTimeList = new ArrayList<>();
>
> List<Pair> endTimeList = new ArrayList<>();
>
> int cameronLastTask = 0;
>
> int jamieLastTask = 0;
>
> String result = "";
>
>
>> for(int x=0; x<activities; x++) {
>
> int start = scan.nextInt();
>
> int end = scan.nextInt();
>
> startTimeList.add(start);
>
> endTimeList.add(new Pair(end, x));
>
> }
>
> Collections.sort(endTimeList);
>
> for(Pair p : endTimeList) {
>
> int endTime = p.getKey();
>
> int index = p.getValue();
>
> int startTime = startTimeList.get(index);
>
> if (startTime >= cameronLastTask) {
>
> plannedSchedule[index]='C';
>
> cameronLastTask = endTime;
>
> } else if (startTime >= jamieLastTask) {
>
> plannedSchedule[index]='J';
>
> jamieLastTask = endTime;
>
> } else {
>
> result = "IMPOSSIBLE";
>
> break;
>
> }
>
> }
>
> if(result.isEmpty()) result = new String(plannedSchedule);
>
> System.out.printf("Case #%d: %s%n", test, result);
>
> }
>
> }
>
>
>> private static class Pair implements Comparable{
>
> private int key;
>
> private int value;
>
> public Pair(int key, int value) {
>
> this.key = key;
>
> this.value = value;
>
> }
>
>
>> public int getKey() {
>
> return key;
>
> }
>
>
>> public int getValue() {
>
> return value;
>
> }
>
>
>> @Override
>
> public int compareTo(Object o) {
>
> if(o instanceof Pair) {
>
> Pair other = (Pair) o;
>
> return Integer.compare(this.key, other.key);
>
> } else {
>
> throw new IllegalArgumentException();
>
> }
>
> }
>
> }
>
> }
>
>
In the code above, if I sort the startTime instead then it will
pass...Please help why this approach does not work. Thanks all.
--
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/74b2a27a-31ca-405e-b3ee-ec7f4bcfcb9e%40googlegroups.com.
