Finding the spots furthest away from bad data
I am going to assume you want to maximize the "separation".  In particular, I'll say that a solution has separation $\ge s$ if every selected place is at least $s$ apart from any selected place, and if every selected place is at least $s$ away from any bad place.

Then this can be solved in $O(m \lg (m/n))$ time using binary search and a greedy algorithm, where $m = $ the data size.  I'll show how to determine whether it's possible to place $n$ stations achieving separation $\ge s$, in $O(m)$ time; then you can use binary search on $s$ to find the largest $s$ achievable.

To determine whether separation $\ge s$ is achievable, just use a greedy algorithm with a left-to-right scan.  Select the left-most place you can.  Then, scanning left to right, select the first place that can be selected (taking into account it has to be at least $s$ to the right of the one you previously selected, and at least $s$ away from any bad place).  Keep iterating.  When you're done, that gives you the maximum number of places that can be selected, subject to the requirement that you have separation $\ge s$.

Now you can use binary search from here.  If the number of places that could be selected was less than $n$, decrease $s$ and try again.  If the number of places that could be selected was greater than or equal to $n$, increase $s$ and try again.  There are at most $m/n$ possible values of $s$, so after $\lg (m/n)$ steps of binary search, this will terminate.  If you start the binary search at the smallest possible value of $s$, the running time will be $O(m \lg s)$.