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
icon
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.

 

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:

  1. In each call, each of them chooses one activity
  2. Jack has to choose an activity that has not been selected yet.
  3. 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.
  4. 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. 
  5. 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. 

 

  1. Sort the activities in ascending order of time in an array
  2. Create a stack or priority queue for Jack’s current chosen task. 
  3. Initialize index to 0.
  4. Create variables for sequence, Jack’s hours and Jill’s hours
  5. For each character c in the call string
    1. If (c==”J”)
      1. Push value of the index of sorted array in the stack/priority queue
      2. Append the value in the sequence
      3. Increment index
      4. Add the value to Jack’s hours
    2. else if  (c==”j”)
      1. Pop the top of the stack or highest value from the priority queue
      2. Append the popped value in the sequence
      3. Add the popped value to Jill’s hours
  6. Print sequence, Jack’s hours, and Jill’s hours

 

Expert Solution
trending now

Trending now

This is a popular solution!

steps

Step by step

Solved in 3 steps with 2 images

Blurred answer
Knowledge Booster
Single source shortest path
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.
Similar questions
Recommended textbooks for you
Database System Concepts
Database System Concepts
Computer Science
ISBN:
9780078022159
Author:
Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:
McGraw-Hill Education
Starting Out with Python (4th Edition)
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
Digital Fundamentals (11th Edition)
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
C How to Program (8th Edition)
C How to Program (8th Edition)
Computer Science
ISBN:
9780133976892
Author:
Paul J. Deitel, Harvey Deitel
Publisher:
PEARSON
Database Systems: Design, Implementation, & Manag…
Database Systems: Design, Implementation, & Manag…
Computer Science
ISBN:
9781337627900
Author:
Carlos Coronel, Steven Morris
Publisher:
Cengage Learning
Programmable Logic Controllers
Programmable Logic Controllers
Computer Science
ISBN:
9780073373843
Author:
Frank D. Petruzella
Publisher:
McGraw-Hill Education