C++ code Beats at least 80% of total, sometimes beats 100% :P


  • 0
    J

    The logic is simple:

    1. take as many classes as possible by each single date.
    2. if multiple classes end on the same date, take the one with shortest duration first.

    if we have data: [[duration1, date1], [duration2, date2],[duration3, date3],...]

    We need to sort the input date in two ways in one priority queue:
    a. sort the data from least "date number" to the greatest.
    b. if there are multiple classes have the same "date number", sort them by the "duration number" from the least to greatest.

    class Solution {
    private:
    
    	struct Small {//what I am talking about in the note above
    		constexpr bool operator()(pair<uint32_t, uint32_t> const & a, pair<uint32_t, uint32_t> const & b) const noexcept
    		{
    			return a.second > b.second||(a.second > b.second&&a.first> b.first);
    		}
    	};
    
    	struct Big {//will explain later
    		constexpr bool operator()(pair<uint32_t, uint32_t> const & a, pair<uint32_t, uint32_t> const & b) const noexcept
    		{
    			return a.first < b.first;
    		}
    	};
    
    public:
    	int scheduleCourse(vector<vector<int>>& courses) {
    
    		if (courses.size() == 0)
    		{
    			return 0;
    		}
    
    		uint32_t total = 0, counter = 0; //total == sum of all the "duration" of all the classes we had taken; 
                                                     //counter == number of classes we had taken
    		priority_queue<pair<uint32_t, uint32_t>, vector<pair<uint32_t, uint32_t>>, Small> _pools;
    		priority_queue<pair<uint32_t, uint32_t>, vector<pair<uint32_t, uint32_t>>, Big> _using;
    
    		for (size_t i = 0; i < courses.size(); ++i)
    		{
    //sort the data, so we can use them later
    				_pools.push(pair<uint32_t, uint32_t>(courses[i][0], courses[i][1]));
    		}
    
    		while (!_pools.empty())//start to decide whether to take the class in the "_pools" or not
    		{
    			if (total + _pools.top().first <= _pools.top().second) //check can we finish all the classes by the end date
    			{
    				total += _pools.top().first;
    				_using.push(_pools.top());//if we can, push it to "_using", which means: total == sum of "duration" of all data in this priority.
    
    //the queue "_using" sorts the data based on the "duration", from the greatest to the least. Therefore, if we cannot finish all the classes in {"_using" AND the _pools.top()}, we remove the data with the greatest "duration" in "_using" and try again to see that can we take the pop.top() or not. 
                     
    				counter++;//increment, no need to explain
    			}
    			else
    			{
    //now, we check that can we finish all the classes in {"_pools.top()" AND ("_using.pop()")}
    //      * if ("duration" of _pools.top()) > ("duration" of _using.top()), then there is no way we can take the "_pools.top()". It will be explained at the bottom
    				if (!_using.empty() && _using.top().first > _pools.top().first)
    				{//if we can take "_pools.top()", then replace "_using.top()" with it. In this case we don't do increment since we are "replacing". Otherwise, gave up the "_pools.top()".
    					total -= _using.top().first;
    					pair<uint32_t, uint32_t> tmp = _using.top();
    					_using.pop();
    					total += _pools.top().first;
    					_using.push(_pools.top());
    				}
    			}
    
    			_pools.pop();
    		}
    
    		return counter;
    	}
    };
    
    

    The reason why there is no way we can take the "_pools.top()" if ("duration" of _pools.top()) > ("duration" of _using.top()):

    Since we sorted the data, the "date" of "_pools.top()" is greater or equal to "date" of "_using.top()":

    • case "date" of "_pools.top()" == "date" of "_using.top()":
      It violates the logic "2. if multiple classes end on the same date, take the one with shortest duration first".
    • case "date" of "_pools.top()" > "date" of "_using.top()":
      If there exist classes that we gave up for taking "_using.top()", chances are, we can take them now since we gave up "_using.top()", which also violated the rule "2. if multiple classes end on the same date, take the one with shortest duration first" and the new class we can take cannot be more than one. One of the solutions is:
    
    class Solution {
    private:
    	struct Big {
    		constexpr bool operator()(pair<uint32_t, uint32_t> const & a, pair<uint32_t, uint32_t> const & b) const noexcept
    		{
    			return a.first < b.first;
    		}
    	};
    	struct Small {
    		constexpr bool operator()(pair<uint32_t, uint32_t> const & a, pair<uint32_t, uint32_t> const & b) const noexcept
    		{
    			return a.second > b.second || (a.second > b.second&&a.first> b.first);
    		}
    	};
    
    	struct SmallDate {
    		constexpr bool operator()(pair<uint32_t, uint32_t> const & a, pair<uint32_t, uint32_t> const & b) const noexcept
    		{
    			return a.first> b.first;
    		}
    	};
    public:
    	int scheduleCourse(vector<vector<int>>& courses) {
    
    		if (courses.size() == 0)
    		{
    			return 0;
    		}
    
    		uint32_t total = 0, counter = 0;
    		map<uint32_t, priority_queue<pair<uint32_t, uint32_t>, vector<pair<uint32_t, uint32_t>>, SmallDate>> m;
    		priority_queue<pair<uint32_t, uint32_t>, vector<pair<uint32_t, uint32_t>>, Small> _pools;
    		priority_queue<pair<uint32_t, uint32_t>, vector<pair<uint32_t, uint32_t>>, Big> _using;
    
    		for (size_t i = 0; i < courses.size(); ++i)
    		{
    			//if (courses[i][1] >= courses[i][0])
    			//{
    				_pools.push(pair<uint32_t, uint32_t>(courses[i][0], courses[i][1]));
    
    			//}
    		}
    
    		while (!_pools.empty())
    		{
    			if (total + _pools.top().first <= _pools.top().second)
    			{
    				total += _pools.top().first;
    				_using.push(_pools.top());
    				counter++;
    			}
    			else
    			{
    				if (!_using.empty() && _using.top().first > _pools.top().first)
    				{
    					total -= _using.top().first;
    					pair<uint32_t, uint32_t> tmp = _using.top();
    					_using.pop();
    					total += _pools.top().first;
    					_using.push(_pools.top());
    
    					if (m.find(tmp.second) != m.end())
    					{
    						while (!m[tmp.second].empty() && total + m[tmp.second].top().first <= _pools.top().second)
    						{
    							total += m[tmp.second].top().first;
    							_using.push(m[tmp.second].top());
    							counter++;
    						}
    					}
    				}
    				else
    				{
    					m[_pools.top().second].push(_pools.top());
    				}
    			}
    
    			_pools.pop();
    		}
    
    		return counter;
    	}
    };
    
    

    0_1499690044404_2017-07-10.png


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.