Maximum Perimeter Triangle

  • + 0 comments

    This question can easily be solved by sorting the sticks array but when you are likely to only examine the top few elements in the array, I prefer to use a priority queue for faster run time.

    void maxPerimeter(int *sticks, int n, int *ans) {
        heapify(sticks, n);
        ans[2] = sticks[0];
        popTop(sticks, &n);
        ans[1] = sticks[0];
        popTop(sticks, &n);
        ans[0] = sticks[0];
        popTop(sticks, &n);
        while (ans[0] + ans[1] <= ans[2]) {
            if (n == 0) {
                ans[0] = -1;
                return;
            }
            ans[2] = ans[1];
            ans[1] = ans[0];
            ans[0] = sticks[0];
            popTop(sticks, &n);
        }
    }