Did the whole thing in a day. Lvl 86 3 boxer.
First started just killing all the camps. Then read notes here and started concentrating on bridge and beach.
Maleko spawned once on the land side of the bridge and twice in the hut on the other side of the bridge with the hole in it. Took her awhile to spawn, maybe an hour...then she spawned twice in 20-30 minutes.
I was doing a rotation of running to the bridge, clearing, running back to other goblin camp.
Other goblin camp I would clear all 4 main sections...cave, hangar, beach, house...in that order. By the time I was done, I'd run to the bridge. Maleko was much faster. The rest of the day I spent trying to get Lutzan. I would clear all 4 areas and then repeat. All 3 times he spawned in huts. I stopped and only cleared beach based on notes here, but he didn't spawn after 2 hours. So I started clearing again. He spawned first in left hut on second shelf, not the 2 far ones to the left but the left of the 3 in the middle (when facing huts from the beach). Then another 90 long minutes went by. Then next two times he spawned in the right-most hut on second level after only about 20-30 minutes.
These have such a quick respawn time that it's really just about patience with the monotony.