Social security, Medicare, and Medicaid are properly termed "entitlements", not "cost centers". You're right that non-discretionary spending dwarfs discretionary spending though.
Yes, you just need to maintain a stack of rectangles ordered from lowest to highest. You only ever have to push and pop the top of the stack, so the runtime is O(n).