The travel industry overbooks - rental cars, hotels, airlines. It's SOP. Yes, it's annoying when it happens, but it's SOP.
At least they informed you - something that hotels and airlines do not do.
I've been called multiple times about airline oversells - in fact they've offered vouchers to compensate for rebookings. Sometimes days before and dozens of times on the day of travel. Surely I can't be the only one?