D
D
Dima Ovcharenko2014-10-14 08:50:52
Algorithms
Dima Ovcharenko, 2014-10-14 08:50:52

Which algorithm to choose for drawing the organizer?

There is a finite number of some abstract tasks (for example, these are tasks assigned for today to one of the specialists in the service desk system). Each task has a clearly defined start time and end time. This time is set at intervals of, say, 30 minutes. Tasks intersect, that is, it is possible that three different tasks are scheduled to be performed from 11:30 to 12:00.
It is necessary to draw a table, where the rows are the time, and the columns are the tasks. The illustration below will help you understand the principle.
6003a7161ffa45ef8a92c0f1c7d19409.PNG
An interesting point is this: each task tends to occupy all available columns.
If the task does not intersect with any other task, it will take up n = 6 columns (task A).
If the task intersects with one more task and only with it - each will take n/2=3 columns (tasks G and H).
Moreover, if one of the tasks already occupies m=2 columns, then the other should occupy nm=4 columns (problems E and F).
Questions to be solved:
1) find out in advance the total number of columns n
2) which task to place in which columns
I will not specifically describe the approach that I have already tested so as not to mislead
anyone the simplest examples. Maybe I'll tell you later.
I suspect that in general the task is reduced to the most "dense" placement of segments without intersections on several axes. By implementing a similar algorithm, I can solve two subtasks at once - find out the number of columns n and the assignment of tasks to columns.
Any ideas? Where to look?

Answer the question

In order to leave comments, you need to log in

1 answer(s)
S
Sergey Romanov, 2014-10-14
@Serhioromano

It's not all that simple here. Sometimes tasks need to be stacked on top of each other. What if at some point, there are more than 7 tasks at one time and you have 6 columns. Or there are 5 of them, how will you divide?
It is necessary to calculate all time intervals on the layout and each event must have 2 properties. 1 - sorting. This is what the event on the segment is in terms of the number if you take from 00 to 24. And the second is with how many events it intersects.
Based on these 2 numbers, you need to make a margin from the left. I think the number of intersections / sorting is suitable for this, and for the width, only the number of intersections.

Didn't find what you were looking for?

Ask your question

Ask a Question

731 491 924 answers to any question