iPhone区間スケジューリング

区間スケジューリング問題をそれっぽくgreedy algorithmで解くiPhoneアプリのサンプルコードを描いてみます。

#import “ViewController.h”

#import <SpriteKit/SpriteKit.h>

#include <memory>

#include <utility>

#include <algorithm>

using namespace std;

class ScheduleSolver {

public:

    void solve(NSArray *);

private:

    pair<int, int> interval[1000];

    int taskCount;

    void greed();

    void notify(pair<int, int>);

};

void ScheduleSolver::solve(NSArray *tasks) {

    taskCount = (int)tasks.count;

    for (int i=0; i <taskCount ; i++) {

        interval[i].first = [[((SKLabelNode *)tasks[i]).name componentsSeparatedByString:@” “][4] intValue];

        interval[i].second = [[((SKLabelNode *)tasks[i]).name componentsSeparatedByString:@” “][2] intValue];

    }

    greed();

}

void ScheduleSolver::greed() {

    sort(interval, interval + taskCount);

    

    int ans = 0, last = –1;

    for (int i=0; i<taskCount; i++) {

        if (last < interval[i].second)  {

            ans++;

            last = interval[i].first;

            

            // notify;

            notify(interval[i]);

        }

    }

}

void ScheduleSolver::notify(pair<int, int> task) {

    [[NSNotificationCenter defaultCenter] postNotificationName:@”my message” object:@[@(task.first), @(task.second)]];

}

@interface ViewController ()

@property SKScene *scene;

@end

@implementation ViewController

– (void)viewDidLoad {

    [super viewDidLoad];

    [self setupScene];

    [self createTitle];

    [self createTaskLine];

    

    [[NSNotificationCenter defaultCenter] addObserver:self selector:@selector(receiveMessage:) name:@”my message” object:nil];

}

– (void)setupScene {

    SKView *sv = [[SKView alloc] initWithFrame:self.view.bounds];

    SKScene *s = [SKScene sceneWithSize:sv.frame.size];

    s.backgroundColor = [UIColor colorWithHue:0.35 saturation:0.02 brightness:1 alpha:1];

    [sv presentScene:s];

    [self.view addSubview:sv];

    

    self.scene = s;

}

– (void)createTitle {

    SKLabelNode *title = [SKLabelNode labelNodeWithText:@”Interval scheduling problem”];

    title.fontSize = 25;

    title.fontName = [UIFont boldSystemFontOfSize:0].fontName;

    title.fontColor = [UIColor greenColor];

    title.position = CGPointMake(CGRectGetMidX(self.view.bounds), CGRectGetMaxY(self.view.bounds) – 150);

    [self.scene addChild:title];

}

– (void)createTaskLine {

    

    int l;

    for(int i=0; i<10; i++) {

        l = 50;

        

        while (l > 5) {

            

            int interval = MAX(arc4random() % MIN(l, 15), 3);

            SKNode *intervalLine = [SKNode node];

            intervalLine.position = CGPointMake((50 – l) * 6 + 50, i * 40 + 100);

            [self.scene addChild:intervalLine];

            

            SKSpriteNode *line = [SKSpriteNode spriteNodeWithColor:[UIColor grayColor] size:CGSizeMake(interval * 6, 2)];

            line.name = @”line”;

            line.anchorPoint = CGPointMake(0, 0.5);

            line.name = [NSString stringWithFormat:@”line start %d finish %d”, 50-l, 50-l + interval];

            [intervalLine addChild:line];

            

            // +2 space

            l -= interval + 1;

        }

    }

}

– (void)touchesBegan:(NSSet *)touches withEvent:(UIEvent *)event

{

    NSMutableArray *tasks = [NSMutableArray array];

    for (SKNode *n in self.scene.children) {

        SKNode *line = [n childNodeWithName:@”line*”];

        if (line) {

            [tasks addObject:line];

        }

    }

    

    shared_ptr<ScheduleSolver> cppClass(new ScheduleSolver());

    cppClass->solve(tasks);

}

– (void)receiveMessage:(NSNotification *)note {

    static int count = 0;

    

    dispatch_after(dispatch_time(DISPATCH_TIME_NOW, (int64_t)(count * 1 * NSEC_PER_SEC)), dispatch_get_main_queue(), ^{

        SKSpriteNode *n = (SKSpriteNode *)[self.scene childNodeWithName:[NSString stringWithFormat:@”//line start %d finish %d”, [note.object[1] intValue], [note.object[0] intValue]]];

        n.color = [UIColor redColor];

        

        [n runAction:[SKAction scaleXTo:1 y:3 duration:0.5]];

    });

    

    ++count;

}

@end