uestion below 11. USE PYTHON LANGUAGE. READ INPUT FROM FILE (NAME THE FILE "input.txt') The problem needs to be solved using Greedy Algorithm Strategy. Jack and Jill’s parents decide to make their children do some house chores. So they list a set of activities that can be completed in a whole day. In order to complete each activity a certain amount of time (in hours) is required. The parents randomly call each of their children several times separately to choose from the given activities. In each call the children choose an activity based on the following conditions:
USE PYTHON LANGUAGE.
READ INPUT FROM FILE (NAME THE FILE "input.txt')
The problem needs to be solved using Greedy
Jack and Jill’s parents decide to make their children do some house chores. So they list a set of activities that can be completed in a whole day. In order to complete each activity a certain amount of time (in hours) is required. The parents randomly call each of their children several times separately to choose from the given activities. In each call the children choose an activity based on the following conditions:
- In each call, each of them chooses one activity
- Jack has to choose an activity that has not been selected yet.
- Jill, being very little, should choose an activity that Jack has already chosen so that she can help her older brother because she cannot do such tasks by herself.
- Jack does not like doing chores, so he decides he would choose the activity that requires the shortest amount of time to complete among the remaining activities.
- Jill really adores her brother and wants to help him out the most she can, so in each call she decides to choose the activity that needs the maximum time to complete out of the activities chosen by Jack so far.
Implement a greedy algorithm that will meet all above conditions. The input will be N- the number of tasks, followed by a sequence of N numbers denoting the time it takes to complete each task and then a call string which is a string of characters only containing J or j representing who is called next Jack (J) or Jill (j). The input format will be:
N
T₁ T₂…… Tn
JJjJjjJ
Assume that both the children will be called and Jack will be called either the same or greater number of times than Jill. You should output the sequence of tasks chosen and the total hours each of the children will be working. Sample input output is given below. You should read from a file. Name the file “input.txt”. Sample input output is given below:
|
Input 1:- 4 1 4 2 3 JJjJjjJ |
Input 2:- 3 2 5 3 JjJJjj |
|
Output1:- 1223314 Jack will work for 10 hours Jill will work for 6 hours |
Output 2: 223553 Jack will work for 10 hours Jill will work for 10 hours |
A possible greedy algorithm for the above problem is discussed below.
- Sort the activities in ascending order of time in an array
- Create a stack or priority queue for Jack’s current chosen task.
- Initialize index to 0.
- Create variables for sequence, Jack’s hours and Jill’s hours
- For each character c in the call string
- If (c==”J”)
- Push value of the index of sorted array in the stack/priority queue
- Append the value in the sequence
- Increment index
- Add the value to Jack’s hours
- else if (c==”j”)
- Pop the top of the stack or highest value from the priority queue
- Append the popped value in the sequence
- Add the popped value to Jill’s hours
- Print sequence, Jack’s hours, and Jill’s hours????.
Step by step
Solved in 2 steps with 2 images
