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

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

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Related questions

Question

100%

USE PYTHON LANGUAGE.

READ INPUT FROM FILE (NAME THE FILE "input.txt')

The problem needs to be solved using Greedy Algorithm Strategy.

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:

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:-

1 4 2 3

JJjJjjJ

Input 2:-

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

Expert Solution

Trending now

This is a popular solution!

Step by step

Solved in 3 steps with 2 images

SEE SOLUTION Check out a sample Q&A here

Knowledge Booster

Learn more about

Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.