The REAL Sorting Problem thread

[cafeenman]

Here's the situation:

You have several rectangles of various heights. All are the same width - doesn't matter.

The top (Y position) of each rectangle is fixed - it can't be changed. If you were to put these rectangles in one column, many of them would overlap. That is not allowed.

Your job is to arrange the rectangles into the fewest number of columns possible.

OK, that's my job, but I don't know how to do it programically, so I need help. Anyone know how to do this?

[phinds]

are you saying that you know the algorithm but don't know how to program it, or are you saying you don't know the algorithm?

There has to be another condition in the statement of the problem, otherwise you (1) can just put them all in one column head to tail or (2) you must put them each in their own column.

[cafeenman]

I'm saying I don't know the algorithm.

They can't go in one column because some of them will over lap. Any rectangles that don't overlap can go in the same column. They need to be arranged as efficiently as possible without overlap. The vertical position of each rectangle is fixed and so is the height of the rectangle.

[phinds]

OK, I think I get the picture now. I was looking at it quite differently at first.

I'm pretty confident that there is no general algorithm that will solve this problem, but if there is, it will include something like this:

(1) get the column with the tallest rectangle and then find the tallest other rectangle that can be legally added to the same column and move it there.

(2) repeat (1) until that column is full, then block that column from further consideration.

(3) repeat (1) and (2) until you can't do any more.

[KayJay]

Do the initial Top-Left Values ensure that they do not overlap by default?

[cafeenman]

I think phinds is on it. This is what I'm trying to accomplish. They are appointments.



I already have the grid and appointment system worked out. All I need to do is arrange the appointments properly and I'm 95% finished.

[KayJay]

All right. I get the picture now.

[WorkHorse]

Originally posted by KayJay
All right. I get the picture now.

After he posts a picture.

This is an evil proffesor's dream question. I haven't a clue. Hope that helps.

Just moving the tallest columns won't work. You have colums with length 1, 2, 3, 4. If can combine 4 & 3 and 2 & 1 overlap you get 3 columns. But if 4 & 2 can combine and 3 & 1 can combine you have only 2.

I'm guessing just checking every possible combination is out of the question.

This strikes me as something that could be done with recursion--probably somehow . I've see LordRat do great stuff with recursion. The problem revolves around getting all the numbers the way you want. Maybe try the Math forum and see if they can work out a mathematical algorithm.

Don't be a brain tease. Post the solution if you find one. I'd love to see it. Sorry I couldn't actually help. Here, I'll roll my eyes one more time.

[cafeenman]

dude, I've posted this question in several different ways time and again in this forum. This is the first time I ever even got a reply. I have put it in maths forums. It's a tough problem.

I could go back and dig up all the threads where I've posted it, but what's the point?

You're right about the problem though. It's trickier than it looks. I hate evil professors. I wish I could get my hands on the Microsoft source for arranging their appointments in Outlook.

If I solve the problem with or without help, I'll post the source. I think the easiest way to work it out is to use lines just to simplify the coding until it works. Then convert it to rectangles.

[cafeenman]

I'm wondering why NotLKH hasn't tried this one out. He seems to enjoy this kind of stuff.

[nemaroller]

Basically, you have this critera:

1) The earliest appointment with the smallest scheduled time comes first.
 if the next earliest appointment will overlap it, it gets shifted into the next column.
 else,
 if it doesnt overlap,
   it gets put in its place in the same column.  
 Move on to the next earliest appoinment, repeat

After done with that column, that is, no other appointments can 
fit in it, you now have to start the organization of the next column 
with the left-over appts, starting with the earliest appointment 
with the shortest time scheduled.

correct? (I suppose you could flip it all, and start the first column
with the earliest appointment that has the longest time scheduled)

[cafeenman]

I don't think that solves it because of what you said in your earlier post. If the next earlier appointment doesn't work in the next column but it will fit in the first column, that doesn't necessarily make it the best fit. It's like saying, "Well, we made an effort to improve it but it didn't work out so we're giving up and putting it where ever it fits."

Hey... keep working on it though. I'm really starting to think this might be a brute force problem. Like you said, try every combination. I don't know how many possible combinations there can be for one day. I mean how many appointments could be in a day?

Then there's the next problem: What about appointments that go more than one day? I think in that case, we just split it up into separate appointments and deal with the portion of a given day as it's own entity.

Or maybe I can just convince my users to not have appointments. They can just free style. Everyone's a walk-in

[cafeenman]

On second thought, you may have this problem pegged. Looking at the pic I posted, that's exactly what's going on. I'm going to play around with appointments in outlook and see if it always does that. if so, that's the approach I'll try. I was wrong about them all being the same width though. You can see in the image that one appointment is a double wide. Must be an appointment for rich rednecks.

[nemaroller]

It seems to me that the picture you posted looks well sorted, other than appt8 being wider than the others..and appt6 and app7 should be swapped with app5

But it also appears you want it to flow out like a triangle

*
***
****
*****
  ****   
    ***

Which would mean you would first sort it as phinds said,
then you would have to devise other code to sort it so it
looks good.

Lol.... wow ...

[cafeenman]

I just know that NotLKH will come in here take a look at, start talking in concepts that I couldn't possibly understand, add a handful of posts showing all the theory behind what he did and end up with three lines of code that handles the whole thing.

Seriously, I've been trying to figure this problem out (off and on) for over 2 years. What you've said already is better than anything I came up with.

[cafeenman]

The appointments are each an instance of a class implementing a label control. There are a couple ways I can go about it.

I could have the columns in a base 1 scheme - column 1 is the first column instead of column 0. Then I can add a class property Column that I set when the appointment has a home.

From there, this is a recursive algorithm. If the appointment's column is greater than 0, then don't consider it because it's already in place.

The other way to do it is with an array that that holds the column. I won't ever need to know the column again because any time an appointment is changes, all the appointments get sorted again. To change an appointment, they just double-click the label or select a label and then click a toolbar item. If I were doing this using graphical methods, I'd definitely need to remember which appointment is in which column.

[nemaroller]

Well, heck...
just try emailing him:
http://209.120.143.185/member.php?s=...m&userid=17089

[cafeenman]

Originally posted by nemaroller
Well, heck...
just try emailing him:
http://209.120.143.185/member.php?s=...m&userid=17089

I did that a couple months ago. He said "Hmm.. interesting problem. I don't have an answer off the top of my head. I'll think on it." I think he promptly forgot about it after that.

I think you actually have the answer though. The next step for me is to use my highly scientific verification method of adding a dozen appointments to outlook in as many ways and see if it always sorts the same way. If it follows the rules you seem to have picked up on, then that's my answer.

I couldn't write an algorithm before because I couldn't figure out what the rules were.

[nemaroller]

I've been playin with outlook also,
and if you have two appointments that start at the same time, but one is scheduled for longer, it comes first.

But if the shorter appointment is moved up in start time, it comes first.

So it actually tries to fit the longer scheduled appointment in the first column, sorting from earlist and longest first, which I think was backwards from the way i was describing.

[gaffa]

Love these problems....

Got a slight change to the previous approach...

1. Sort the appointments by time.

2. Loop through and place in the first available position. Check each column until you find a match. Create a new column if necessary.

3. Done

I've just done a similar problem - box stacking wit hboxes of diffecent sizes. Heaps of fun - easy to make it work, hard to make it fast and get the best result.

You could use genetic algorithms here - change mutate the sort order befroe you place.

- gaffa

[SLH]

As a bit of extra help/info. What you are discribing is a 'bin packing' algorythm.

There are several algorythms available, and i was taught them last year. Infortunatly i've since had the exams and so erased most of it from my memory.

I can, however remember 2 of the algorythms.
One is called 'Best-Fit'. You loop through each appointment, and see which can fit into the column (bin), leaving the least space. You continue to do this, looping through each appointment, and each column, until you have placed every appointment.

The other i remember is called the 'Worst-Fit' Algorythm. You do the same as before, except choose the appointment that would leave the most space in the bin.

I expect that if you posted a thread in the maths forum, you'd get a lot of helpful replys, as i learnt the above algorythms as part of a maths course.

[cafeenman]

The real application this goes in is not in any shape to test this out easily. I need to rewrite a lot of the appointment code before I can actually do this. Also, I have implemented 3 views (1 day, 5 day and 7 day) so I'm going to have to figure out a way to loop through each day. This code is just for one day.

Am I overlooking anything here? I think it does what nemaroller suggested:

Option Explicit
 
Private db As Database
Private colAppointments As New Collection
Private MaxCols As Integer
 
Private Sub FetchAppointments()
Dim sSQL As String
Dim RST As Recordset
 
' I know this is a BS query :)
sSQL = "SELECT Today's Appointments FOR Dr. Smith ORDER BY StartTime ASC, Len(EndTime - StartTime) DESC"
Set RST = db.OpenRecordset(sSQL)
 
With RST
  .MoveLast
  MaxCols = .RecordCount
  .MoveFirst
  Do Until .EOF
    Dim Appointment As New cAppointment
    Appointment.ProviderID = !ProviderID
    Appointment.EndTime = RoundHalfHour(!EndTime)
    Appointment.StartTime = RoundHalfHour(!StartTime)
    Appointment.Column = 0
    colAppointments.Add Appointment
    .MoveNext
  Loop
End With
 
End Sub
Private Sub ShowAppointments()
 
End Sub
Private Sub SortAppointments()
Dim i As Integer
Dim j As Integer
 
colAppointments(1).Column = 1
 
For i = 2 To colAppointments.Count
  With colAppointments(i)
    .Column = 1
    For j = 1 To i - 1
      If (.Column = colAppointments(j).Column) And _
        (.StartTime < colAppointments(j).EndTime) And _
        (.EndTime > colAppointments(j).StartTime) Then
 
          ' Move to next column
          .Column = colAppointments(j).Column + 1
      End If
    Next j
  End With
Next i
 
End Sub
Private Sub Form_Load()
 
FetchAppointments
SortAppointments
ShowAppointments
 
End Sub

[beachbum]

I think this is the second time I have caught u attempting programming Coffee Man!

Ok since I am lazy and prefer concepts to be described in simple terms can u explain a few things to me... (if it has already been asked and answered in thread then GFY! )

What is the X axis each day? ie you have a number of columns.. are they rooms? people? activities? what? I guess it cant be that hard since surely u will only be able to have one person in one place at any one time... or maybe I am not even on the same wavelength as ur problem... please explain in kindergarten words

[cafeenman]

Each person will have their own schedule. So the picture above is for one person on one day.

From what I've seen, people often have overlapping appointments on the same day. Sometimes the appointments are appointments so much as they are reminders for something going on that day. In any case, the schedule needs to have the ability to overlap appointments even if they can't be at more than one at the same time.

And the question is still unresolved.