If Office_id is the primary key of Office, make sure it has a (primary key) index. This will definitely speed up the adding of the constraint.
Also, according to How can I temporarily disable a foreign key constraint in MySQL?How can I temporarily disable a foreign key constraint in MySQL?, you can use
SET FOREIGN_KEY_CHECKS=0;
To disable ALL foreign key constraint checks, possibly this works too when adding them.