Introduction to Greedy Algorithms and Activity Scheduling Problem

What are greedy algorithms and solution of activity problem using greedy algorithm


Category: Data Structure And Algorithms Tags: C#, Java, C++ Programming

Activity Scheduling Problem Code Files

Introduction

        Suppose we have list of some activities with start time and finish time, where finish times are already in sorted order f1<f2<f3…<fi and we need to schedule events such a way we can utilize conference hall for maximum possible hours.
Greedy Algorithms: A greedy algorithm makes choice which is best at moment. Unlike dynamic programming it won’t store any solutions of any sub problems. Greedy algorithms don’t consider any long term benefits and it best fits for some problems like activity/event scheduling.

Implementation

        Observe below code carefully:

public class SchedulingManager
{
public int[] _startTime;
public int[] _finishTime;
public SchedulingManager(int[] startTime, int[] finishTime)
{
_startTime = startTime;
_finishTime = finishTime;
}

public string GreedyScheduling(int[] start, int[] finish)
{
string s = "A1, "; //scheduling first activity always
int k = 0;

for (int i = 1; i < finish.Length; i++)
{
if (start[i] >= finish[k]) //scheduling next activity as soon as comes
{
//found activity which has grater start time than last activitiy's finish time
s += string.Format("A{0}, ", i + 1);
k = i; // setting last scheduled activity index
}
}
return s;
}
}

Above we are having two arrays one is having start times of activities and other one is having finish times. GreedyScheduling schedules first Activity (A1) by default and then finds immediate activity which has grater or equal start time than previously scheduled activity’s finish time. We will execute above code:

static void Main(string[] args)
{
SchedulingManager demo = new SchedulingManager
(new int[] { 3, 4, 3, 6, 5, 9 }, new int[] { 5, 5, 6, 12, 14, 18 });
//A1(3,5), A2(4,5), A3(3,6), A4(6,12), A5(5,14), A6(9,18)

string scheduledEvents = demo.GreedyScheduling(demo._startTime, demo._finishTime);
Console.WriteLine(scheduledEvents);
Console.ReadLine();
}

Above we had six activities A1(3,5), A2(4,5), A3(3,6), A4(6,12), A5(5,14), A6(9,18) to schedule, Output will be:
A1, A4,


Like 0 People
Last modified on 31 October 2018
Nikhil Joshi

Nikhil Joshi
Ceo & Founder at Dotnetlovers
Atricles: 133
Questions: 9
Given Best Solutions: 9 *

Comments:

No Comments Yet

You are not loggedin, please login or signup to add comments:

Existing User

Login via:

New User



x