The idea is to store the current min value or its index for each push.
And the push could be at O(1) complexity because it only need to compare the new element with the previous min value.
Finally the pop and the min functions are quite straightforward.
Quick&dirty pseudo code only:
template<class T> class RegularStack
{
public:
RegularStack(){...}
push(T NewElement){...}
T pop(){...}
bool bIsEmpty(){...}
protected:
vector<T> mao_StackData; // Stack data container.
};
template<class T> class MinStack: public RegularStack<T>
{
public:
MinStack():RegularStack(){...}
push(T NewElement)
{
if( bIsEmpty() )
mao_MinStackData.push_back(0);
else
mao_MinStackData.push_back( T < peek( mao_MinStackData[ui_GetCount()-1] ) ? ui_GetCount() : ui_GetCount()-1 );
RegularStack<T>::push(T);
}
T pop()
{
mao_MinStackData.pop_back();
return RegularStack<T>::pop();
}
T min()
{
assert( !bIsEmpty() );
return peek( maul_MinIndices[ui_GetCount()-1] );
}
protected:
unsigned int ui_GetCount()
{
return mao_StackData.size();
}
T peek(unsigned int index)
{
assert(index < ui_GetCount() );
return mao_StackData[index];
}
vector<unsigned int> maul_MinIndices; // Each element holds the index to the min element of the corresponding stack level.
};
Basic concept:
For this kind of scheduling problem, since there are many local minimal during the search, there's no way to use a global solution which converge. It means solutions like A* or genetic algorithm won't help to find the optimal best solution.
To really find the optimal best solution, we really have to test all possibilities, which is extemely time-consuming. It's the reaon why here they don't ask to find an optimal solution, instead, they only ask to find one working solution.
So here I would like to suggest an experimental solution as below.
And it's possible to use a simpler experimental solution in order to make it faster or more robust, so the solution here is only for illustrative purpose.
The observation is:
We could always try to run these tasks with minimal R( if several tasks have the same R, choose the one with the maximal O ), until some new tasks whese O exceed the current remaining time.
At this point, we must cancel the previous task, and choose one new task whese O exceeds.
Here the tricky part, we should NOT choose the task with biggest O, because it works for this task, but it could fail later on for another task with big O.
Therefore we are supposed to choose the task with the smallest R among these tasks with exceeding O.
But at the end, it could still fail, and the solution is to cancel some already scheduled taskes until it works.
If one already scheduled task has an even bigger O than the current task with problem, it makes no sense to cancel it, and it means the scheduling is bound to fail.
The solution is:
1) Try to run first the task with minimal R, if the new remaining time is still enough for the maximum O of all the remainning tasks.
2) However, if there's NO enough new remaining time for any remaining task:
A) Find all remainning tasks whose maximum O is smaller than the previous remaining time, but bigger than the new remaining time. It's guarenteed to find at least one.
B) Pick the one with the minimal R, and run it.
3) Enter into the next iteration, and if there's one remaining task whose O is bigger than the current remaining time, try to cancel previously scheduled taskes one by one.
4) If everything are cancelled, it fail.
class Task
{
public:
Run();
int O;
int R;
};
class TaskSet
{
public:
TaskSet(){...};
Task *GetTaskWithMaxO();
Task *GetTaskWithMinR_ThenWithMaxO();
Task *GetTaskWithMinR_WithOinRangeXY(x,y);
bool bAnyRemainingTaskWithBiggerMaxO();
void RemoveTask(Task *);
private:
vector<Task *> mapo_Tasks;
};
提升卡
沉默卡
喧嚣卡
千斤顶
楼主 
谢谢啦
您老人家太牛了
