CODEWITHSUNDEEP
algorithmgantt-chart
Divyanshu Varma
Divyanshu Varma

Reputation: 132

Algorithmic/programming approach to Gantt chart problem

I have 6 processes P1, P2, P3, P4, P5, and P6. I also have their start times and duration given in the problem.

process# start duration
1        1     1
2        3     1
3        0     6
4        5     2
5        5     4
6        8     1

Now I have to find out the maximum of number of completely non-overlapping processes. Two processes are completely non-overlapping if one does not overlap the other at any point in time.

So I made a Gantt chart and it is easy to see that the answer is 4. P1, P2, P4 and P6 are completely non-overlapping. Gantt chart

Now I have to write a program to compute the same. On a Gantt chart I can easily 'see' the solution. In the algorithm for my program, I don't know how to minimise the time complexity: currently I'm thinking about taking each process and comparing its start and end times with other processes, but that roughly makes it O(n^2). If I scale up the processes from 6 to say 1000, O(n^2) will take a huge time.

Is there any standard way of doing such problems - I mean such problems that are easy to visualise - like Gantt charts? Otherwise how do I make this algorithm better, any suggestions?

Upvotes: 0

Views: 619

Answers (1)

Surt
Surt

Reputation: 16099

There are different paths that you could take to find a solution, here are some in no particular order.

  • Is that already a solution on the net?

Most likely, important point, Gantt chars are essentially intervals.

  • Could it be a graph problem?

Consider that each interval is a node, imaging a start node at 0 (zero) and connect all nodes to all nodes starting later than its end. Use Dijkstra or A* like to find a solution.

  • Could it be a dynamic programming problem?

Are there subproblems, yes, add or don't add an interval, repeat.

  • Do I know a data structure that is used in this kind of problems?

Yes, Augmented Interval Tree can it be used for this problem, maybe.

Upvotes: 1

Related Questions