data structures - Greedy Algorithm for Finding Min Set of Intervals that Overlap All Other Intervals -

-

i'm learning greedy algorithms , came across problem i'm not sure how tackle. given set of intervals (a,b) start time , end time b, give greedy algorithm returns minimum amount of intervals overlap every other interval in set. example if had:

(1,4) (2,3) (5,8) (6,9) (7,10)

i return (2,3) , (7,8) since these 2 intervals cover every interval in set. have right this:

  1. sort intervals increasing end time
  2. push interval smallest end time onto stack
  3. if interval (a,b) overlaps interval on top of stack (c,d) (so less d) if a<=c keep (c,d). else update interval on top of stack (a,d)
  4. if interval (a,b) not overlap interval on top of stack (c,d) push (a,b) onto stack
  5. at end stack contains desired intervals , should run in o(n) time

my question is: how algorithm greedy? i'm struggling concepts. maybe have right , maybe don't, if do, can't figure out greedy rule is/should be.

edit: valid point made below, should have been clearer about. (7,8) works instead of (1,10) (which covers everything) because every time in (7,8) in (5,8) (6,9) , (7,10). same (2,3), every time in there in (1,4) , (2,3). goal set of intervals such if looked @ possible times in set of intervals, each time in @ least 1 of original intervals.

a greedy algorithm 1 repeatedly chooses best incremental improvement, though might turn out sub-optimal in long run.

your algorithm doesn't seem greedy me. greedy algorithm problem be:

  1. find interval contained in largest number of intervals input set.
  2. remove intervals input set contain it.
  3. repeat until input set empty.

for example, first produce (7,8), because contained in 3 input intervals, reduce input set (1,4)(2,3), produce (2,3)

note algorithm doesn't produce optimal output input set: (0,4)(1,2)(1,4)(3,6)(3,7)(5,6)

it produces (3,4) first, since covered 4 input intervals, best answer (1,2)(5,6), covered 3 intervals each


Comments

Post a Comment

Popular posts from this blog

javascript - Chart.js (Radar Chart) different scaleLineColor for each scaleLine -

-
Image
i try , create radar chart using chart.js has various colours each scaleline, or coloured between scalelines. wondering if possible? from: to: i have working graph, though there doesn't seem method change individual scale lines. kind regards leigh you can extend radar chart type this, so chart.types.radar.extend({ name: "radaralt", initialize: function (data) { chart.types.radar.prototype.initialize.apply(this, arguments); var originalscaledraw = this.scale.draw; var ctx = this.chart.ctx; this.scale.draw = function () { var linewidth = this.linewidth; // bypasses line drawing in originalscaledraw this.linewidth = linewidth; originalscaledraw.apply(this, arguments); ctx.linewidth = this.linewidth; var scale = this; // draw chart.helpers.each(scale.ylabels, function (label, index) { // color of ...
Read more

apache - Error with PHP mail(): Multiple or malformed newlines found in additional_header -

-
suddenly have started receiving above error without changes having been made script. host 1and1 (i know...) the script still works fine on different server, , suspicion there must have been server config change has lead this, although hosts plead ignorance. there's no information on above error @ in google can find - have ideas? server running apache if helps. had similar problem. came out of blue. no php code changed. what changed: php upgraded 5.5.25-1 5.5.26. a security risk in php mail() function has been fixed , newlines in additional_headers allowed no more. because newlines mean: starts email message (and surely don't want inject newlines through headers followed evil message). what have worked fine, e.g. having newlines after headers or passing whole message additional_headers , function no more. solution : sanitize headers. no multiple newlines in additional_headers argument. these count "multiple or malformed newlines":...
Read more

java - Android – MapFragment overlay button shadow, just like MyLocation button -

-
Image
i'm struggling add shadow custom overlay button on google map. goal make custom button google's mylocation button. here's how app looks now: layout.xml <relativelayout xmlns:android="http://schemas.android.com/apk/res/android" xmlns:tools="http://schemas.android.com/tools" xmlns:map="http://schemas.android.com/apk/res-auto" android:layout_height="match_parent" android:layout_width="match_parent" style="@style/apptheme"> <fragment android:layout_width="match_parent" android:layout_height="match_parent" android:id="@+id/map" tools:context=".mapsactivity" android:name="com.google.android.gms.maps.supportmapfragment" android:layout_alignparentend="true" android:layout_alignparentstart="true" android:layout_alignparentbottom="true" ...
Read more