Re^2: Convex Hull Problem

The problem statement is updated.

Hm. Still woolly. Does that mean you can run (service, maintain) two 'events' that overlap, provided that they do not start at the exact same time?

Ie. You can 'do' b through e if you skip a?

 8     9    10    11    12     1     2     3     4     5
 aaaaaaaaaaaaaaaaaaa
 bbbbbbbbbbbbbbbbbbbbbbbbb
       ccccccccccccccccccc
             ddddddddddddddddddd
          eeeeeeeeeeee
[download]

With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.

"Science is about questioning the status quo. Questioning authority".

In the absence of evidence, opinion is indistinguishable from prejudice.

Comment on Re^2: Convex Hull Problem Download Code

Replies are listed 'Best First'.
Re^3: Convex Hull Problem by code-ninja (Scribe) on Aug 27, 2013 at 09:59 UTC
No. Events may overlap and in such a case, I'll have to select the one with the highest cost. Keep in mind that "cost" here refers to the income I'll get for each event. Consider my example. `1 4 6 1 2 10 2 4 9 ...` [download] The first event transcends the start of the third event, right? But I'm selecting the second because it does not clash with any other and gives me maximum cost. OTOH, if the input would've been: `1 5 2 1 2 5 2 4 9 ...` [download] The first even transcends the other two but I ignore it and select `2 4 9` because the event takes less time and is more profitable. I hope its clearer now. If not, let the problem statement rest and comment on the algorithm that I coded. I'll search for the exact problem statement and repost this question. My apologies, but this question bugs me periodically and for a while I get really intense about solving it and get carried away. :).	[reply] [d/l] [select]
Re^4: Convex Hull Problem by BrowserUk (Patriarch) on Aug 27, 2013 at 10:21 UTC
The first event transcends the start of the third event, right? By "transcend" do you mean 'overlaps'? And why is that a question. Are you unsure? I hope its clearer now. If not, let the problem statement rest and comment on the algorithm that I coded. Sorry, but quite how you've selected a convex hull algorithm applied to a 2D reduction of 3D coordinate system as an appropriate approach to solving what seems to be a very simple scheduling problem, is quite beyond me. Reducing start & end times to a time period throws away all the inter-dependancy information between events, renders any results produced devoid of any time-based restrictions. And conflating a time period with money as a 2D coordinate is the proverbial mixing of apples and oranges. (Simpler to divide money by time to get a single number and sort.) Quite frankly, I don't see any application for convex hulls to the problem description; so I'll back-the-f-off and leave you to it. With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday' Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error. "Science is about questioning the status quo. Questioning authority". In the absence of evidence, opinion is indistinguishable from prejudice.	[reply]