If there are three tasks that conflict in the same period of time, then it is impossible, yes. But consider this input: 1 4 0 100 400 500 0 300 200 600
A working allocation is to put tasks 1 and 4 on one parent and 2 and 3 on the other. But by processing them in the original order and always assigning to C if there is no conflict yet, your program puts tasks 1 and 2 on C, and then 3 on J, and task 4 has nowhere to go. Sorting is not the only way to solve this problem, but if you are doing a greedy algorithm where you just assign each task to any parent available, you need to sort by start times to avoid problems like this. Do keep in mind that you have to retain the original order when you sort in order to produce the correct output. On Mon, Apr 6, 2020 at 8:42 PM Atta Mohamed <[email protected]> wrote: > - why I got the wrong answer with this code? > - do we need sorting? > - I assumed that if three activities overlap with each other so the there > is no solution is this assumption correct? > > > > import java.io.BufferedReader; > import java.io.InputStreamReader; > import java.util.ArrayList; > import java.util.HashSet; > import java.util.Iterator; > import java.util.List; > import java.util.Scanner; > import java.util.Set; > > public class Solution { > > class Activity { > > Integer startTime; > Integer endTime; > > public Integer getStartTime() { > return startTime; > } > > public void setStartTime(Integer startTime) { > this.startTime = startTime; > } > > public Integer getEndTime() { > return endTime; > } > > public void setEndTime(Integer endTime) { > this.endTime = endTime; > } > > public Activity(Integer startTime, Integer endTime) { > super(); > this.startTime = startTime; > this.endTime = endTime; > } > public boolean hasConflicWith(Activity activity) { > if (this.startTime < activity.endTime && activity.startTime < > this.endTime) > return true; > return false; > } > } > > static boolean hasConflictsWith(List<Activity>activities,Activity > activity) { > > for (int i = 0; i < activities.size(); i++) { > if(activities.get(i).hasConflicWith(activity)) > return true; > } > return false; > } > > public static void main(String[] args) { > Solution problem3 =new Solution(); > // TODO Auto-generated method stub > Scanner in = new Scanner(new BufferedReader(new > InputStreamReader(System.in))); > int t = in.nextInt(); // Scanner has functions to read ints, longs, > strings, chars, etc. > for (int i = 1; i <= t; ++i) { > > int n = in.nextInt(); > List<Activity> activities = new ArrayList<Solution.Activity>(); > for (int j = 0; j < n; j++) { > activities.add(problem3.new Activity(in.nextInt(), in.nextInt())); > } > List<Activity> JActivities = new ArrayList<Solution.Activity>(); > List<Activity> CActivities = new ArrayList<Solution.Activity>(); > String solution = ""; > for (int j = 0; j <n; j++) { > if(!hasConflictsWith(CActivities, activities.get(j))) { > CActivities.add(activities.get(j)); > solution += "C"; > continue; > > } > if(!hasConflictsWith(JActivities, activities.get(j))) { > JActivities.add(activities.get(j)); > solution += "J"; > continue; > } > solution = "IMPOSSIBLE"; > break; > } > > System.out.println("Case #" + i + ": " + solution); > > } > > } > > } > > -- > 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/c7c94f00-55a3-44f9-b01a-ed9a47c08cf5%40googlegroups.com > <https://groups.google.com/d/msgid/google-code/c7c94f00-55a3-44f9-b01a-ed9a47c08cf5%40googlegroups.com?utm_medium=email&utm_source=footer> > . > -- 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/CAMAzhzgY8qgDkig5Yzjk6OTw7mknNHzPAkWbjHhcEUwHAsShwA%40mail.gmail.com.
