My "Textbook" Style Solution Using Heapsort


  • 0
    D

    The code was written in C++.
    ...
    class Solution {
    public:
    // Main algorithm.
    int findMinDifference(vector<string>& timePoints) {
    heap_sort(timePoints);
    unsigned int minD = time_minus(timePoints[0], timePoints[timePoints.size() - 1]);
    for (unsigned int i = 0; i < timePoints.size() - 1; i++)
    if (time_minus(timePoints[i], timePoints[i + 1]) < minD) minD = time_minus(timePoints[i], timePoints[i + 1]);
    return (int)minD;
    }

    // Compare two "hh:mm" strings.
    friend bool operator < (const string& time1, const string& time2) {
    	if (stoi(time1.substr(0, 2)) < stoi(time2.substr(0, 2))) return true;
    	if (stoi(time1.substr(0, 2)) > stoi(time2.substr(0, 2))) return false;
    	return stoi(time1.substr(3)) < stoi(time2.substr(3));
    }
    
    friend bool operator > (const string& time1, const string& time2) {
    	if (stoi(time1.substr(0, 2)) > stoi(time2.substr(0, 2))) return true;
    	if (stoi(time1.substr(0, 2)) < stoi(time2.substr(0, 2))) return false;
    	return stoi(time1.substr(3)) > stoi(time2.substr(3));
    }
    
    // Subtraction of two time strings.
    unsigned int time_minus(const string& time1, const string& time2) {
    	if (time1 < time2) return time_minus(time2, time1);
    	unsigned int result = (stoi(time1.substr(0, 2)) - stoi(time2.substr(0, 2))) * 60 + stoi(time1.substr(3)) - stoi(time2.substr(3));
    	return result > 720 ? 1440 - result : result;
    }
    
    // Heapsort.
    template<typename Item_Type>
    void max_heapify(vector<Item_Type>& A, unsigned int arr_length, unsigned int i) {
    	unsigned int left_child = 2 * i + 1, right_child = 2 * i + 2;
    	unsigned int largest = i;
    	Item_Type swapTemp;
    	if (left_child < arr_length && A[left_child] > A[largest]) largest = left_child;
    	if (right_child < arr_length && A[right_child] > A[largest]) largest = right_child;
    	if (largest != i) {
    		swapTemp = A[i];
    		A[i] = A[largest];
    		A[largest] = swapTemp;
    		max_heapify(A, arr_length, largest);
    	}
    }
    
    template<typename Item_Type>
    void build_max_heap(vector<Item_Type>& A, unsigned int arr_length, unsigned int i) {
    	unsigned int left_child = 2 * i + 1, right_child = 2 * i + 2;
    	if (left_child < arr_length) build_max_heap(A, arr_length, left_child);
    	if (right_child < arr_length) build_max_heap(A, arr_length, right_child);
    	max_heapify(A, arr_length, i);
    }
    
    template<typename Item_Type>
    void heap_sort(vector<Item_Type>& A, unsigned int arr_length) {
    	build_max_heap(A, arr_length, 0);
    	Item_Type swapTemp;
    	for (unsigned int i = arr_length - 1; i > 0; i--) {
    		swapTemp = A[0];
    		A[0] = A[i];
    		A[i] = swapTemp;
    		arr_length--;
    		max_heapify(A, arr_length, 0);
    	}
    }
    
    template<typename Item_Type>
    void heap_sort(vector<Item_Type>& A) {
    	heap_sort(A, A.size());
    }
    

    };
    ...


Log in to reply
 

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