What you have done is correct. In general there can be many URIs to the same resource - there are no rules that say you shouldn't do that.
And generally, you may need to access items directly or as a subset of something else - so your structure makes sense to me.
Just because employees are accessible under department:
company/{companyid}/department/{departmentid}/employees
Doesn't mean they can't be accessible under company too:
company/{companyid}/employees
Which would return employees for that company. It depends on what is needed by your consuming client - that is what you should be designing for.
But I would hope that all URLs handlers use the same backing code to satisfy the requests so that you aren't duplicating code.