assign points to non-overlapping rectangles
Most spatial indexes should be good, especially if your rectangles are axis aligned. 

Spatial indexes typically have about $O(log{M})$ insertion time so you could build in index in $O(M * log{M})$.
Lookup time is similar, so finding the best/correct rectangle for every point should be around $O(N * log{M})$.

For rectangles, the simplest index is probably a quadtree (but may not scale as well with larger $M$). R-Trees such as the R*Tree (R-Star-Tree) are harder to implement but probably better than plain quadtrees. You could also look into STR-Trees (sort-tile-recurse-loaded R-Trees), they take longer to build but have faster lookup.

In case you are using C++, have a look at libSpatialIndex or the Boost R-Tree. If you are using Java, have a look at my TinSpIn library. In the case of Java I can also strongly recommend the PH-Tree (disclaimer: self advertisement).