区間スケジューリング問題をそれっぽく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