Absolutely doable. With some nuances.
This assumes that Department is a consistent variable between AD and your organizational hierarchy. This will be a text based exact match. So for some organizations, this is a high hurdle to pass.
You also need to feed userids into the contacts application. The RUM tool (available on the community) contains some utilities to support this function. I recommend feeding the UserID into Contacts twice, once as a read only, and once as an edit authority so you can subjectively inherit later.
Then you'll need a calculated cross reference field located on the contacts app, pointing to the departments app that will merge based on the text being exactly the same between the Contact's Department, and the department name of the Department record. Make sure to also include a limiter in there so that NULL value in either don't create references.
Lastly, you'll need to set up inheritances to the department record from the related contacts application through the newly designed cross reference field. I recommend creating two references, one for Edit, one for Read Authority, so you can subjectively inherit to other solutions.
Now you'll have the inherited contacts record permission reflected at the department level to inherit to downstream use cases that need to grant access explicitly based on access.
