"I tried 'integrate' already. It
worked in terms of removing gaps, but
also generalized all polygons
according to specified cluster
The question is whether you want to keep the 'Grey' polygons separated as they are now.
In order to NOT generalize the boundaries you might have to do this the long way, you could Union -> Spatially Select all polygons from the result whose centroid falls within the original purple polygon -> Merge selection
At this point you will have the 'Grey' fetures unalteres and the 'purple' polygon following exactly around the 'Grey' where there was an overlap.
This will still leave you with the gaps; if you are merging all of the 'Grey' features into one then use a similar procedure: create another polygon feature on a separate layer that overlaps all the 'gaps' and union. (Or use another technique to fill the gaps)
Now the gaps will be filled with features with no attributes. You could refer to these as slivers. If all features are to be merged to a single 'Purple' feature then select all 'slivers' and merge to purple. To do it the other way around and the only way to somehow automate the process at this point is by using a tool that merges sliver polygons to it's neighbors or best manually.
There are tools that can eliminate slivers by merging them to the largest adjacent polygon (more ideally in combination with attribute criteria) (http://arcscripts.esri.com/details.asp?dbid=14672) However, I would strongly recommend to find a tool/script that merges slivers to the adjacent polygon that it shares the longest boundary with. This can be done programatically with ArcObjects but i don't know if a tool that does this is available. These algorithms can get quite complex when you get into problems like stacked slivers, etc. I've never tried the mentioned tool so i don't know how it deals with real nasty situations like stacked slivers (needs to be recursive) or whether you can enter attribute criteria...