in reply to Convex Hull Problem

Problem statement: I'm given a set of points, each point being a 3-tuple (x, y, z) where x is the start time of an event, y is the end time of that event and z is the money earned if that event is scheduled/takes place. Now, it is not necessary that all events start or end at a mutually exclusive times. Events may overlap, like A(3, 4, 5) and B(3, 8, 5). Given a set of such events, I've to find a schema such that if the events are scheduled in that order, I'll get the maximum profit.

Your problem description leaves me cold.

If there is no constraint on events overlapping; scheduling them all will maximise profits?

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.

Replies are listed 'Best First'.
Re^2: Convex Hull Problem
by SuicideJunkie (Vicar) on Aug 26, 2013 at 19:46 UTC

    I think that means that there are events that overlap, and are thus mutually exclusive. If none of the events overlap, then you could just choose all of them.

    What I don't get is:

    Problem statement: I'm given a set of points, each point being a 3-tuple (x, y, z) where x is the start time of an event, y is the end time of that event and z is the money earned if that event is scheduled/takes place. Now, it is not necessary that all events start or end at a mutually exclusive times. Events may overlap, like A(3, 4, 5) and B(3, 8, 5). Given a set of such events, I've to find a schema such that if the events are scheduled in that order, I'll get the maximum profit.
    Why would it matter what order you pick the events? Surely at the end you should just have a set of events which you have chosen and a second set which you have rejected.

[reply]

      Hm. Doesn't your "are thus mutually exclusive" conflict with his " it is not necessary that all events start or end at a mutually exclusive times."?

      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]

        The interpretation depends on whether that is referring to the events as inputs, or as outputs.

        I think we need to wait for OP clarification.

[reply]

In Section Seekers of Perl Wisdom