Last active
August 29, 2015 14:01
-
-
Save oieioi/dc75dc2d244b1fa24450 to your computer and use it in GitHub Desktop.
CodeIQチケットゴブル問題写経 https://gist.github.com/hyuki0000/6273a52b9454ccfca095
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/usr/bin/env coffee | |
fs = require 'fs' | |
_ = require 'lodash' | |
class Ticket | |
constructor: (@country, fromMonth, fromDay, toMonth, toDay) -> | |
if fromMonth > toMonth | |
throw "invalid" | |
else if fromMonth is toMonth and fromDay >= toDay | |
throw "invalid" | |
@first = fromMonth * 100 + fromDay | |
@last = toMonth * 100 + toDay | |
isInclude: (e) -> @first <= e <= @last | |
isConflict: (r) -> | |
@isInclude(r.first) or @isInclude(r.last) or r.isInclude(@first) or r.isInclude(@last) | |
class Solver | |
constructor: (fileName) -> | |
text = fs.readFileSync fileName, encoding: 'utf-8' | |
lines = text.split '\n' | |
@requests = [] | |
for line in lines | |
if not line? then break | |
try | |
country = line.match(/^[^ ]+/)[0] | |
days = line.match(/\d+\/\d+/g) | |
from = days[0].split '/' | |
to = days[1].split '/' | |
@requests.push new Ticket country, +from[0], +from[1], +to[0], +to[1] | |
solve : -> | |
result = [] | |
rs = @requests.sort (a, b) -> | |
if a.last is b.last then return 0 | |
if a.last < b.last then return -1 | |
if a.last > b.last then return 1 | |
while rs.length isnt 0 | |
r = rs.shift() | |
# かぶった予定を削除 | |
rs = _.reject rs , (item) -> r.isConflict item | |
result.push r | |
countries = for item in result then item.country | |
countriesSorted = countries.sort() | |
"#{result.length} #{countriesSorted.join(' ')}" | |
sol = new Solver './tickets.txt' | |
console.log sol.solve() |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment